%gmChap07.tex

\graphicspath{{./figures/chapter07/}}

\chapter{Contrast-Invariant Monotone Operators as Sup-Inf Operators}

The main contents of this chapter are two representation theorems: one for translation-invariant monotone set operators and one for functions operators that are monotone, contrast invariant, and translation invariant. If $T$ is a function operator satisfying these three conditions, then it has a ``sup-inf'' representation of the form
\[
Tu(\fxx)=\sup_{B\in\mathcal B} \inf_{\fxy\in B}u(\fxx+\fxy),
\]
where $\mathcal B$ is a family of subsets of $\mathcal P(\RR^N)$, the set of all subsets of $\RR^N$. This theorem is a nonlinear version of the Riesz theorem that states that a continuous linear translation-invariant operator can be represented as a convolution
\[
Tu(\fxx)=\int_{\RR^N}u(\fxx-\fxy)k(\fxy)\,\rmd\fxy.
\]
In this case, the kernel $k$ is called the impulse response. In the same way, $\mathcal B$ is an impulse response for the nonlinear operator.

\section{Translation-invariant monotone set operators}

The translation operators $\tau_{\fxx}$ were defined for sets and functions in section 6.1 and translation invariance for set operators and function operators was defined in Definition 6.4.

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

\begin{exercise} 
Prove that $\mathcal T\RR^N=\RR^N$ if  $\mathcal T$ is translation invariant  and $\mathcal T\RR^N\ne\emptyset$.\finex
\end{exercise}

We consider a translation-invariant monotone set operator $\mathcal T$ defined on a family of sets  $\mathcal L\subset\mathcal P(\RR^N)$. We will always assume that $\mathcal L$ is closed under translation and that $\RR^N\in\mathcal L$, and to avoid the trivial case, that $\mathcal T \RR^N\ne\emptyset$. 

\begin{theorem}[Matheron] Let $\mathcal T$ be a translation-invariant monotone set operator acting on a family of sets $\mathcal L$ that contains $\RR^N$, and assume that $\mathcal T \RR^N\ne\emptyset$. Then $\mathcal T$ can be represented by
\begin{equation}\label{eq81}
\mathcal T X=\bigcup_{B\in\mathcal B}\bigcap_{\fxy\in B}(X-\fxy)=\{\fxx\mid\fxx+B\subset X \text{ for some }B\in\mathcal B\},
\end{equation}
where $\mathcal B=\{X\mid 0\in\mathcal TX\}$. Conversely, if $\mathcal B$ is any nonempty subset of $\mathcal P(\RR^N)$, then formula \eqref{eq81} defines a translation-invariant monotone set operator on $\mathcal P(\RR^N)$.
\end{theorem}

\begin{proof}We first check that 
$
\bigcup_{B\in\mathcal B}\bigcap_{\fxy\in B}(X-\fxy)=\{\fxx\mid\fxx+B\subset X \text{ for some }B\in\mathcal B\},
$
where $\mathcal B$ is any subset of $\mathcal P(\RR^N)$ and $X$ is any subset of $\RR^N$. If $\fxx\in\bigcup_{B\in\mathcal B}\bigcap_{\fxy\in B}(X-\fxy)$, then for some $B\in\mathcal B$, $x\in X-\fxy$ for all $\fxy\in B$. This means that $\fxx+B\subset X$, and hence $\fxx\in\{\fxx\mid\fxx+B\subset X \text{ for some }B\in\mathcal B\}$. Now assume that $\fxx+B\subset X \text{ for some }B\in\mathcal B$. Then $\fxx\in X-\fxy$ for all $\fxy\in B$, which proves that $\fxx\in\bigcup_{B\in\mathcal B}\bigcap_{\fxy\in B}(X-\fxy)$.

Now let $\mathcal B=\{X\mid 0\in\mathcal T X\}$. (Note that $\mathcal B\ne\emptyset$.) The proof of the main part of the theorem is given by a chain of equivalence relations, which we number to indicate where the assumptions are used:
\begin{align*}
\fxx\in\mathcal T X&\stackrel{\mathrm(1)}{\Longleftrightarrow}0\in\mathcal T X-\fxx\stackrel{\mathrm(2)}{\Longleftrightarrow}0\in\mathcal T(X-\fxx)\stackrel{\mathrm(3)}{\Longleftrightarrow}X-\fxx\in\mathcal B\\
&\stackrel{\mathrm(4)}{\Longleftrightarrow} X-\fxx=B\text{ for some }B\in\mathcal B\stackrel{\mathrm(5)}{\Longleftrightarrow}\fxx+B\subset X\text{ for some }B\in\mathcal B.
\end{align*}
The equivalence (2) follows from the translation invariance of $\mathcal T X$; (3) is just the definition of $\mathcal B$; and (4) is a restatement of (3). The implication from left to right in (5) is obvious. The implication from right to left in (5) is the point where the monotonicity of $\mathcal T$ is used: Since $B\subset X-\fxx$, it follows from the monotonicity of $\mathcal T$ that $X-\fxx\in\mathcal B$. This proves \eqref{eq81}.

Given any family of sets $\mathcal B$, it is possible to define a set operator $\mathcal T:\mathcal P(\RR^N)\to\mathcal P(\RR^N)$ by \eqref{eq81}. Using the representation $\mathcal T X=\{\fxx\mid\fxx+B\subset X \text{ for some }B\in\mathcal B\}$ it is easy to check that $\mathcal T$ is monotone and translation invariant.
\end{proof}

The next exercise shows that $\mathcal B=\{X\mid0\in\mathcal T X\}$ is not the only set that can be used to represent $\mathcal T$.

\begin{exercise}Let the set operator $\mathcal T^{\circ}$ be defined on all elements of $\mathcal P(\RR^N)$ by $\mathcal T^{\circ} X=X^{\circ}$, where $X^{\circ}$ denotes the interior of $X$.
\begin{enumerate}[(i)]\setlength\itemsep{2pt}
\item Show that $\mathcal T^{\circ}$ is monotone and translation invariant.
\item Show that there is a countable set $\mathcal B$ of open sets that generates $\mathcal T^{\circ}$.
\item Show that there are many families $\mathcal B$ of open sets that generate $\mathcal T^{\circ}$. \finex
\end{enumerate}
\end{exercise}

\begin{exercise}Given a nonempty family of sets $\mathcal B\subset\mathcal P(\RR^N)$, we know from Theorem 7.1 that the set operator $\mathcal T$ defined by $\mathcal T X=\bigcup_{B\in\mathcal B}\bigcap_{\fxy\in B}(X-\fxy)=\{\fxx\mid \fxx+B\subset X \text{ for some } B\in\mathcal B\}$ is a translation-invariant monotone operator defined on all of $\mathcal P(\RR^N)$. Assume that $\mathcal B\subset\mathcal L\subset\mathcal P(\RR^N)$, where $\mathcal L$ is translation invariant but otherwise arbitrary. Let $\mathcal B_{\mathcal L}=\{X\mid X\in\mathcal L, 0\in\mathcal T X\}$ and let $\mathcal T_{\mathcal L}$ be the operator generated by $\mathcal B_{\mathcal L}$. Show that $\mathcal T=\mathcal T_{\mathcal L}$ Hint: Show that $B_{\mathcal L}\in\mathcal B_{\mathcal L}$ implies that there is a $B\in\mathcal B$ such that $B\subset B_{\mathcal L}$. Use the fact that $\mathcal T$ and $\mathcal T_{\mathcal L}$ agree on ${\mathcal L}$. Prove the general result: If $\mathcal B$ and ${\mathcal B}\,'$ are two families of sets such that (i) $\mathcal B\subset{\mathcal B}\,'$ and (ii) given $B'\in\mathcal B\,'$ there is a $B\in\mathcal B$ such that $B\subset B'$, then $\mathcal B$ and $\mathcal B\,'$ generate the same set operator $\mathcal T$. \finex
\end{exercise}

The main point of both of these exercises is that $\mathcal T$ is generated by the small sets in $\mathcal B$. Thus if $\mathcal B\subset{\mathcal B}\,'$, then you generate the same operator as long as you do not add sets to $\mathcal B\,'$ that are strictly smaller than sets in $\mathcal B$. This is the point of condition (ii) in Exercise 7.4.

We will be defining both set operators and function operators in terms of sets $\mathcal B$, which are called sets of \textit{structuring elements} in the language of mathematical morphology. In view of the important role commutation plays in image analysis, it is useful to have a test for $\mathcal B$ to determine whether or not the operator $\mathcal T$ can be expected to be upper semicontinuous on a family of sets $\mathcal L$. Not surprisingly, the condition we are going to formulate involves both $\mathcal B$ and $\mathcal L$. As usual, we assume that $\mathcal L$ is closed under translations and that it contains $\bigcap_{\mu<\lambda}X_\mu$ whenever $(X_\lambda)_{\lambda\in\RR}$ is a decreasing chain of sets in $\mathcal L$.

\begin{proposition}The translation-invariant monotone operator in Theorem 7.1 defined by a given set $\mathcal B$ is upper semicontinuous on $\mathcal L$ if and only if the following condition holds: If $\bigcap_{n\in\mathbb N}\mathcal T X_n\ne\emptyset$, then there is a $B\in\mathcal B$ such that $\fxx+B\subset\bigcap_{n\in\mathbb N} X_n$, where $\fxx\in\bigcap_{n\in\mathbb N}\mathcal T X_n$ and $(X_n)_{n\in\mathbb N}$ is any descending sequence in $\mathcal L$.
\end{proposition}
\begin{proof}
The proof in one direction is just the definition of $\mathcal T$. Assume $\mathcal T$ is u.s.c. and that $\bigcap_{n\in\mathbb N}\mathcal T X_n\ne\emptyset$. Then $\mathcal T (\bigcap_{n\in\mathbb N} X_n)=\bigcap_{n\in\mathbb N}\mathcal T X_n$ is not empty. Thus by the definition of $\mathcal T$, for $\fxx\in\mathcal T (\bigcap_{n\in\mathbb N} X_n)$ there is a set $B\in\mathcal B$ such that $\fxx+B\subset\bigcap_{n\in\mathbb N} X_n$.

Now assume that $\bigcap_{n\in\mathbb N}\mathcal T X_n\ne\emptyset$ and take $\fxx\in\bigcap_{n\in\mathbb N}\mathcal T X_n$. Since it is always true that 
$\mathcal T (\bigcap_{n\in\mathbb N} X_n)\subset\bigcap_{n\in\mathbb N}\mathcal T X_n$, we must show that $\fxx\in\mathcal T (\bigcap_{n\in\mathbb N} X_n)$. By hypothesis, there is a $B\in\mathcal B$ such that $\fxx+B\subset\bigcap_{n\in\mathbb N} X_n$. Since $\mathcal T$ is monotone and translation invariant, $\fxx+\mathcal T B\subset\mathcal T (\bigcap_{n\in\mathbb N} X_n)$. The result follows from that fact that $0\in\mathcal T B$. 
\end{proof}

This result is probably more useful in a negative rather than a positive sense. For example, suppose that $\mathcal B$ contains a descending sequence $(B_n)_{n\in\mathbb N}$. (This is not always the case. See Exercise 7.4.) Then $0\in\bigcap_{n\in\mathbb N}\mathcal T B_n$, but there may not be a $B$ such that $B\subset\bigcap_{n\in\mathbb N} B_n$. In this situation, there is no possibility of $\mathcal T$ being u.s.c. on some set $\mathcal L$. A case in point is the operator $\mathcal T^{\circ}$ in Exercise 7.3.

\begin{exercise}Suppose that $\mathcal B$ contains exactly one set. Show that $\mathcal T$ is u.s.c. on $\mathcal P(\RR^N)$. Generalize this to the case $\mathcal B$ contains a finite number of sets. \finex
\end{exercise}

\section{Sup-inf operators}

We are now going to shift the focus from set operators to function operators. The next theorem is the dual to Theorem 7.1.   

\begin{theorem}
Let $T$ be a monotone function operator defined on $\mathcal F$ and assume $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$. Let $\mathcal T$ be the set operator associated with $T$: $\mathcal T X=\levelset_1 T\bmone_X$. For $\fxx\in\RR^N$ and $X\in\mathcal L$, let $\mathcal B_{\fxx}=\{X\mid\fxx\in\mathcal T X\}$. Then for $u\in\mathcal F$,
\begin{equation}\label{eq83}
Tu(\fxx)=\sup_{B\in\mathcal B_{\fxx}}\inf_{\fxy\in B}u(y)\; \text{ for a.e. } \fxx\in\RR^N.
\end{equation}
If $T$ is also translation invariant, then
\begin{equation}\label{eq84}
Tu(\fxx)=\sup_{B\in\fxx+\mathcal B_0}\inf_{\fxy\in B}u(y)\; \text{ for a.e. } \fxx\in\RR^N.
\end{equation}
Conversely, suppose that for every $\fxx\in\RR^N$ there corresponds a nonempty family of sets $\mathcal B_{\fxx}$. Then equation \eqref{eq83} defines a contrast-invariant monotone function operator, and equation \eqref{eq84} defines a contrast-invariant monotone function operator that is also translation invariant. These operators are defined on all functions $u:\RR^N\to\RR$.
\end{theorem}

\begin{proof}
The first thing to observe is that definitions \eqref{eq83} and \eqref{eq84} are not vacuous: By Proposition 6.8$(iii)$, $\mathcal T\RR^N=\RR^N$, so  $\RR^N\in\mathcal B_{\fxx}$ for all $\fxx\in\RR^N$.

For $u\in\mathcal F$, let $\tilde T u(\fxx)=\sup_{B\in\mathcal B_{\fxx}}\inf_{\fxy\in B}u(y)$, where $\mathcal B_{\fxx}=\{X\mid\fxx\in\mathcal T X\}$. We are going to prove that $\tilde T u(\fxx)=Tu(\fxx)$ for a.e. $\fxx\in\RR^N$. We know from Proposition 6.8 that $\levelset_\mu Tu=\mathcal T\levelset_\mu u$ almost everywhere, except possibly for a countable number of $\mu$. We denote this possible exceptional set by $M$. Thus, as in the proof of Lemma 3.8, we can choose a countable dense set $\Lambda$ such that $\Lambda\cap M=\emptyset$ and $\levelset_\lambda Tu=\mathcal T\levelset_\lambda u$ almost everywhere for $\lambda\in\Lambda$. For each $\lambda\in\Lambda$, let $N_\lambda=(\levelset_\lambda Tu\setminus\mathcal T\levelset_\lambda u)\cup(\mathcal T\levelset_\lambda u\setminus\levelset_\lambda Tu)$. Then $N_\lambda$ has measure zero as does the countable union $N=\bigcup_{\lambda\in\Lambda}N_\lambda$. We are going to prove that $\tilde T u(\fxx)=Tu(\fxx)$ for a.e. $\fxx\in\RR^N$ by showing that 
\begin{equation}\label{eq7iff}
\tilde T u(\fxx)\geq\lambda \Longleftrightarrow  T u(\fxx)\geq\lambda 
\end{equation}
for $\lambda\in\Lambda$ and $\fxx\in\RR^N\setminus N$. This means that $\levelset_\lambda \tilde T u=\levelset_\lambda T u$ almost everywhere for all $\lambda\in\Lambda$, and it follows from Lemma 3.8 that $\tilde T u(\fxx)=Tu(\fxx)$ for a.e. $\fxx\in\RR^N$.

The proof of \eqref{eq7iff} consists of a sequence of equivalence relations that are justified in the text following the display. In the following, $\mu$ and $\lambda$ are in $\Lambda$ and $\fxx\in\RR^N\setminus N$.
\begin{align*}
Tu(\fxx)\geq\lambda&\stackrel{\mathrm(1)}{\Longleftrightarrow}Tu(\fxx)\geq\mu \text{ for all } \mu<\lambda\stackrel{\mathrm(2)}{\Longleftrightarrow}\fxx\in\levelset_{\mu} Tu \text{ for all } \mu<\lambda\\
&\stackrel{\mathrm(3)}{\Longleftrightarrow}\fxx\in\mathcal T \levelset_{\mu} u \text{ for all } \mu<\lambda\stackrel{\mathrm(4)}{\Longleftrightarrow}\levelset_{\mu} u\in{\mathcal B}_{\fxx} \text{ for all } \mu<\lambda\\&\stackrel{\mathrm(5)}{\Longleftrightarrow}\text{There is a } B\in{\mathcal B}_{\fxx}\text{ such that }\inf_{\fxy\in B}u(\fxy)\geq\mu\text{ for all }\mu<\lambda\\
&\stackrel{\mathrm(6)}{\Longleftrightarrow}\sup_{B\in{\mathcal B}_{\fxx}}\inf_{\fxy\in B}u(\fxy)\geq\lambda\stackrel{\mathrm(7)}{\Longleftrightarrow}\tilde T u(\fxx)\geq\lambda. 
\end{align*}
Equivalence (1) is just a statement about real numbers, and (2) is just the definition of level set. It is at (3) that we replace $\levelset_{\mu} Tu$ with $\mathcal T \levelset_{\mu}u$ while avoiding the possible exceptional sets $M$ and $N$. Equivalence (4) is just the definition of ${\mathcal B}_{\fxx}$. The implication (5) from left to right is true by taking $B=\levelset_{\mu} u$. The implication from right to left is where the monotonicity of $T$ is used: Since $T$ is monotone, $\mathcal T$ is monotone, and thus it follows directly from the definition of $\mathcal B$ that $B\subset X$ and $B\in{\mathcal B}_{\fxx}$ imply that $X\in{\mathcal B}_{\fxx}$. Assuming the right-hand side of (5), we have $B\subset\levelset_{\mu} u$ for all $\mu<\lambda$. Hence, from what we hve just said, $\levelset_{\mu} u\in{\mathcal B}_{\fxx}$ for all $\mu<\lambda$, which is the left-hand side of (5). Equivalence (6) is another statement about real numbers, and (7) is the definition of $\tilde T$. This completes the proof of \eqref{eq83}.

If $T$ is also translation invariant, then it is clear from Definition 6.4 and the definition of $\mathcal T$ that $\mathcal T$ is translation invariant. This implies that $\mathcal B_{\fxx}=\fxx+\mathcal B_0$ for all $\fxx\in\RR^N$, and \eqref{eq84} follows from \eqref{eq83}.

To prove the converse, define $T$ on $\{u\mid u:\RR^N\to\RR\}$ by
\[
Tu(\fxx)=\sup_{B\in\mathcal B_{\fxx}}\inf_{\fxy\in B}u(y).
\]
The operator $T$ is well defined, since we have assumed that $\mathcal B_{\fxx}$ is not empty. Clearly, $T$ is monotone: If $u\geq v$, then $\inf_{\fxy\in B}u(y)\geq\inf_{\fxy\in B}v(y)$, and it follows that $Tu\geq Tv$. If $g$ is any continuous contrast change, then for any nonempty set $I\subset\RR$, $\inf_{x\in I}g(x)=g( \inf_{x\in I}x)$ and $\sup_{x\in I}g(x)=g( \sup_{x\in I}x)$. This implies that $T$ commutes with $g$. If we replace $\mathcal B_{\fxx}$ with $\fxx+\mathcal B_{0}$, then it is easy to check that $T$ is also translation invariant.
\end{proof}



Theorem 7.2 is a result about $T$ that is based on Proposition 6.8. The set operator $\mathcal T$ enters as a convenience, in the sense that the results can be stated completely in terms of $T$. For example, the proof began with the fact that $\levelset_{\lambda}Tu=\mathcal T\levelset_{\lambda}u$ almost everywhere, with the possible exception of at most a countable number of $\lambda$'s. This is exactly the content of Lemma 6.6, where it is written as $T\gamma_{\lambda}(u)=\gamma_{\lambda}(Tu)$. Lemma 6.6 is based on the facts that $T$ is monotone and invariant under Lipschitz-continuous contrast changes. If we bypass the contrast-invariant assumption and assume that $T$ is monotone and that $T\gamma_{\lambda}(u)=\gamma_{\lambda}(Tu)$ for all $\lambda$ and all $u\in\mathcal F$, then a review of the proof of Theorem 7.2 reveals that \eqref{eq83} is true for all $\fxx\in\RR^N$. Similarly, \eqref{eq84} is true for all $\fxx\in\RR^N$ if we add the hypothesis that $T$ is translation invariant. We state this as a corollary.

\begin{corollary}Let $T$ be a monotone operator defined on a family of functions $\mathcal F$ that includes the functions $\bmone_{\levelset_{\lambda}u}$, $u\in\mathcal F$, $\lambda\in\RR$, and assume that $T\gamma_{\lambda}(u)=\gamma_{\lambda}(Tu)$ for all $\lambda\in\RR$ and all $u\in\mathcal F$. Then $T$ can be represented by
$
Tu(\fxx)=\sup_{B\in\mathcal B_{\fxx}}\inf_{\fxy\in B}u(y)
$
for all $\fxx\in\RR^N$. If $T$ is also translation invariant, then
$
Tu(\fxx)=\sup_{B\in\fxx+\mathcal B_{0}}\inf_{\fxy\in B}u(y)
$
for all $\fxx\in\RR^N$.
\end{corollary}

One may ask, What happened to the contrast-invariance assumption? The answer is that it is implied by the very strong assumption that $T$ commutes with all (upper) thresholds: $T\gamma_{\lambda}(u)=\gamma_{\lambda}(Tu)$. In fact, once we have a sup-inf representation, it is clear from Theorem 7.2 that the operator $T$ is contrast invariant. Furthermore, it can be extended as a contrast-invariant monotone operator to all functions $u:\RR^N\to\barR$. The problem with this is that there is no guarantee that this extension preserves commutation with thresholds. But without some form of commutation with thresholds, the theory is not very interesting or useful for applications. Fortunately, there is a more conservative extension that preserves commutation. Here is how it works:

Let $\mathcal F_g$ denote the set of all functions of the form $g(u)$ where $u\in\mathcal F$ and $g$ is a continuous contrast change. Then $\mathcal F\subset\mathcal F_g$ and $\mathcal F_g$ is closed under continuous contrast changes. Extend $T$ to $\mathcal F_g$ using the sup-inf representation given by Corollary 7.3. We know from the proof of Theorem 7.2 that $g(Tu)=Tg(u)$. Furthermore, the condition $T\gamma_{\lambda}(u)=\gamma_{\lambda}(Tu)$ is preserved with this extension:
\[
\levelset_{\lambda}Tg(u)=\levelset_{\lambda}g(Tu)=\levelset_{g^{(-1)}_\lambda}Tu=\mathcal T\levelset_{g^{(-1)}_\lambda}u=\mathcal T\levelset_{\lambda}g(u).
\]

\begin{corollary}
With the assumptions of Corollary 7.3, the extension of $T$ to $\mathcal F_g$ preserves commutation with thresholds.
\end{corollary}

Theorem 7.2 has a useful semi-converse. It states that given a translation-invariant sup-inf operator $T$ represented with the set of structuring elements $\mathcal B$, the associated set operator $\mathcal T$ can also be represented with $\mathcal B$.

\begin{proposition}Let $T$ be a function operator defined on the set of functions $\mathcal F$ and assume that $\bmone_{\levelset_{\lambda}u}\in\mathcal F$, $u\in\mathcal F$, $\lambda\in\RR$. Let $\mathcal T$ be the associated set operator defined on $\mathcal L$, the set of all level sets of functions in $\mathcal F$, by $\mathcal T X=\levelset_1 T\bmone_X$. If $T$ is represented by
\begin{equation}\label{eq84a}
Tu(\fxx)=\sup_{B\in\fxx+\mathcal B}\inf_{\fxy\in B}u(y),
\end{equation}
where $\mathcal B$ is a nonempty set of structuring elements, then $\mathcal T$ can be represents by
\begin{equation}\label{eq81a}
\mathcal T X=\bigcup_{B\in\mathcal B}\bigcap_{\fxy\in B}(X-\fxy)=\{\fxx\mid \fxx+B\subset X \text{ for some } B\in\mathcal B\}.
\end{equation}
Conversely, if we are given a set operator $\mathcal T$ that is represented by \eqref{eq81a} and if we know that $\mathcal T$ maps measurable sets into measurable sets, then the same set $\mathcal B$ can be used to represent the function operator $Tu(\fxx)=\sup\{\lambda\mid \fxx\in\mathcal T\levelset_{\lambda}u\}$ in the sense that 
\begin{equation}
Tu(\fxx)=\sup_{B\in\fxx+\mathcal B}\inf_{\fxy\in B}u(y) 
\end{equation}
for almost every $\fxx\in\RR^N$.
\end{proposition}

\begin{proof}
We have assumed that $\bmone_{\levelset_{\lambda}u}\in\mathcal F$ for $u\in\mathcal F$. If we had not made this assumption, we could have extended $T$ to these functions using the representation \eqref{eq84a}. Thus, for $X\in\mathcal L$, consider $\mathcal T X=\levelset_1 T\bmone_X$. We see that
\begin{equation*}
\inf_{\fxy\in\fxx+B}\bmone_X(\fxy)=
\begin{cases}
0 \text{ if }\fxx+B\not\subset X,\\
1 \text{ if }\fxx+B\subset X.
\end{cases}
\end{equation*}
Thus, $\sup_{B\in\mathcal B}\inf_{\fxy\in\fxx+B}\bmone_X(\fxy)=1$ if and only if there is a $B\in\mathcal B$ such that $\fxx+B\subset X$, and the  representation \eqref{eq81a} follows directly.

For the converse, assume that we are given the set operator $\mathcal T$ defined by the nonempty family $\mathcal B$. By assuming that $\mathcal T$ maps measurable sets to measurable sets, we can apply Proposition 6.10 and conclude that $\levelset_{\lambda}Tu=\mathcal T\levelset_{\lambda}u$ almost everywhere, with the possible exception of at most a countable set of $\lambda$'s. Here we assume that the operator $T$ is defined by $Tu(\fxx)=\sup\{\lambda\mid\fxx\in\mathcal T\levelset_{\lambda}u\}$. With these conditions, we can repeat the proof of Theorem 7.2 and conclude that 
\begin{equation}\label{eq79}
Tu(\fxx)=\sup_{B'\in\fxx+\mathcal B'}\inf_{\fxy\in B'}u(y) 
\end{equation}
for a.e. $\fxx\in\RR^N$, where $\mathcal B'=\{X\mid 0\in\mathcal T X\}$. We know from Exercise 7.4 that $\mathcal B$ and $\mathcal B'$ generate the same set operator $\mathcal T$ and hence the same function operator $T$.
\end{proof}



With the second half of Proposition 7.5, our point of view shifted to that of ``starting with a set operator $\mathcal T$.'' In this setting, the assumption that a function operator commutes with thresholds is replaced with the assumption that $\mathcal T$ is upper semicontinuous on $\mathcal L$, its domain of definition. Thus, if we assume that a set operator $\mathcal T$ is represented by \eqref{eq81a} and if we assume that $\mathcal T$ satisfies the hypotheses of Theorem 6.12, then we can conclude that the function operator $T$ associated with $\mathcal T$ can be represented by 
\[
Tu(\fxx)=\sup_{B\in\fxx+\mathcal B}\inf_{\fxy\in B}u(y)
\]
for all $\fxx\in\RR^N$, where $\mathcal B$ is the same family of sets used to represent $\mathcal T$.

\begin{exercise}Use these last results to show that the extrema killer $T_a$ can be represented as a sup-inf function operator with the structuring elements 
\[
\mathcal B=\{B\mid B\text{ is compact, connected, meas\,$(B)=a$, and } 0\in B\}. \finex 
\]
\end{exercise}

The sup-inf representation for a function operator $T$ and the ``$\cup\cap$'' representation for a set operator $\mathcal T$ are so general that 
once an operator is represented in one of these forms on a set of functions $\mathcal F$ or a set of sets $\mathcal L$ it can immediately be extended to all functions on $\RR^N$ or all sets $X\subset\RR^N$. This can be a bit dangerous, since, as mentioned above, these extensions cannot be expected to preserve the commutation relation $\mathcal T\levelset_{\lambda}u=\levelset_{\lambda}Tu$, and it is important to maintain this relation for image operators. We saw in the case of the extrema killer that there is commutation in its strongest form, that is, for all $\lambda$ when $\mathcal F$ is the set of continuous functions on $\mathbb T^N$ and $\mathcal L$ is the set of compact subsets of $\mathbb T^N$. In this case, we began with the set operator; in other cases we will be presented with the function operator first and then define the set operator. In all of these cases, we wish to preserve commutation, but to do so it will be necessary to restrict either the family $\mathcal B$ or the domains of definition of $T$ and $\mathcal T$. The next exercise illustrates this problem.

\begin{exercise}
Let $\mathcal B=\{\{\fxx\}\mid\fxx\in D(0,1)\}$, where $D(0,1)=\{\fxx\mid|\fxx|\leq1\}$. Show that $Tu(\fxx)=\sup_{\fxy\in\fxx+D}u(\fxy)$. Let $(q_n)_{n\in\NN}$ be a countable dense set in $\RR^N$ and consider $u$ defined by $u(\fxx)=1-1/n$ if $\fxx=q_n$ and $u(\fxx)=0$ otherwise. Show that $\mathcal T\levelset_1u\ne\levelset_1 Tu$. \finex
\end{exercise}

The operator $T$ in Exercise 7.7 is one of the classic image operators called a \textit{dilation}. We will see in section 7.3 that $T$ will commute with all thresholds when its domain of definition is restricted to upper semicontinuous functions.

We end this section by showing that sup-inf operators can be represented as inf-sup operators.

\begin{proposition}
Assume that $T$ can be represented by $Tu(\fxx)=\sup_{B\in\mathcal B}\inf_{\fxy\in\fxx+B}u(\fxy)$. Then $T$ also has an inf-sup representation
\begin{equation}\label{eq86}
Tu(\fxx)=\inf_{B\in\mathcal B'}\sup_{\fxy\in\fxx+B}u(\fxy),
\end{equation}
where $\mathcal B'$ is a new structuring set.
\end{proposition}
\begin{proof}
The result follows from the axiom of choice, Boolean algebra, and properties of real numbers. A map $\phi:\mathcal B\to\bigcup_{B\in\mathcal B}B$ with the property that $\phi(B)\in B$ is called a \textit{selection function}. (In general, one must invoke the axiom of choice to guarantee the existence of $\phi$.) Let $\mathcal S_{\mathcal B}$ denote the set of all selection functions. We then have
\[
\sup_{B\in\mathcal B}\inf_{\fxy\in B}u(\fxy)=\inf_{\phi\in\mathcal S_{\mathcal B}}\sup_{B\in\mathcal B}u(\phi(B))=\inf_{\phi\in\mathcal S_{\mathcal B}}\sup_{\fxy\in\phi(\mathcal B)}u(\fxy).
\]
For $\phi\in\mathcal S_{\mathcal B}$ write $\phi(\mathcal B)=\bigcup_{B\in\mathcal B}\phi(B)$ and let $\mathcal D=\{\phi(\mathcal B)\mid\phi\in\mathcal S_{\mathcal B}\}$. Then
\[
\sup_{B\in\mathcal B}\inf_{\fxy\in B}u(\fxy)=\inf_{\phi(\mathcal B)\in\mathcal D}\sup_{\fxy\in\phi(\mathcal B)}u(\fxy).
\]
The structuring set $\mathcal D$ thus obtained for the inf-sup representation is not the same one used for the sup-inf representation.
\end{proof}

\section{The Evans--Spruck extension}

We are going to consider a monotone function operator $T$ defined on a family of continuous functions $\mathcal F$ that does not necessarily contain the functions $\bmone_{\levelset_{\lambda}u}$ for $u\in\mathcal F$. We assume that $\mathcal F$ contains a subset of functions $\mathcal F_c$ all of whose level sets are compact. Our goal is to use $T$ to define its associated set operator on all of the compact sets $X=\levelset_{\lambda}u$, where $u\in\mathcal F_c$. To be able to write $\mathcal T X=\levelset_1 T \bmone_{\levelset_{\lambda}u}$, we must extend $T$ to the functions $\bmone_{\levelset_{\lambda}u}=\gamma_{\lambda}(u)$, $u\in\mathcal F_c$. We are going to extend $T$ to these functions by defining $T\gamma_{\lambda}(u)=\gamma_{\lambda}(Tu)$. This means that to have a proper extension (definition) we must show that $\gamma_{\lambda}(u)=\gamma_{\mu}(v)$  implies that $T\gamma_{\lambda}(u)=T\gamma_{\mu}(v)$ for $u,v\in\mathcal F_c$. This is equivalent to showing that $\levelset_{\lambda}u=\levelset_{\mu}v$ implies that $\levelset_{\lambda}Tu=\levelset_{\mu}Tv$ for $u,v\in\mathcal F_c$. 

Until now, when we began with a monotone function operator $T$ on a set of functions $\mathcal F$, we have assumed that $\mathcal F$ contained the functions $\bmone_{\levelset_{\lambda}u}$ for $u\in\mathcal F$. This assumption and the assumption that $\mathcal F$ and $T$ were invariant under Lipschitz-continuous contrast changes were sufficient for developing the theory. To compensate for not assuming that $\mathcal F$ contains the functions $\bmone_{\levelset_{\lambda}u}$, we are going to assume that $\mathcal F$ and $T$ are invariant under all continuous contrast changes. Clearly, the set $\mathcal F_c$ is invariant under these contrast changes.

We prepare to prove that $\levelset_{\lambda}u=\levelset_{\mu}v$ implies $\levelset_{\lambda}Tu=\levelset_{\mu}Tv$ for $u,v\in\mathcal F_c$ by making two simplifications. Since $g(s)=s+\lambda$   is an admissible contrast change, $u\in\mathcal F_c$ if and only if $u+\lambda\in\mathcal F_c$ for any constant $\lambda$, and thus we may assume that $\levelset_{0}u=\levelset_{0}v$. Similarly, we can replace $u$ and $v$ with the functions $g(u)$ and $g(v)$, where $g(s)= \min(s,0)$, and have $\levelset_{0}g(u)=\levelset_{0}u$ and $\levelset_{0}g(v)=\levelset_{0}v$. These simplifications justify the assumptions of the next lemma, which is the key to proving our version of the Evans--Spruck extension.\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}).} 

\begin{lemma}Let $u$ and $v$ be real-valued functions bounded above by zero  and assume that $\levelset_0u=\levelset_0v\,(\ne\emptyset)$. If $u$ is continuous and if the level sets of $v$ are compact for all levels $\lambda\leq0$, then there is a continuous contrast change $h$ such that $h(0)=0$ and $u\geq h(v)$.
\end{lemma}
\begin{proof} Define $\tilde{h}(r)=\min\{u(\fxx)\mid \fxx\in\levelset_r v\}$ for $r\leq0$  and $\tilde{h}(r)=0$ for $r>0$. 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)\in\{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 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 $\limsup 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 of $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 continuous for $r\leq0$ and that $\tilde h\geq h$. Find examples of functions $u$ and $v$ defined on $\RR$ for which $\tilde h$ is not continuous. \finex
\end{exercise}

Everything is now in place to state and prove our version of the Evans--Spruck extension theorem.

\begin{theorem}[Evans--Spruck]Let $T$ be a contrast-invariant monotone function operator defined on a set $\mathcal F$ of continuous functions that is invariant under continuous contrast changes. With these assumptions, it is possible to extend $T$ to the characteristic functions $\bmone_{\levelset_{\lambda}u}$ by the formula $T\bmone_{\levelset_{\lambda}u}=\bmone_{\levelset_{\lambda}Tu}$ whenever the level sets of $u$ are compact.
\end{theorem}
\begin{proof}Our preliminary comments show that it is sufficient to prove that $\levelset_{0}u=\levelset_{0}v$ implies $\levelset_{0}Tu=\levelset_{0}Tv$ when $u$ and $v$ are continuous and bounded by zero and the level sets of $u$ and $v$ are all compact. We assume that $\levelset_{0}u=\levelset_{0}v$ is not empty.

The proof follows directly from Lemma 7.7: Let $h$ be a continuous contrast change such that $h(0)=0$ and $u\geq h(v)$. Since $T$ is monotone and contrast invariant, $Tu\leq0$ and $Tu\geq Th(v)=h(Tv)$. Using the fact that $h(0)=0$, we see that $Tv(\fxx)=0$ implies that $Tu(\fxx)=0$. By interchanging the roles of $u$ and $v$ we see that $Tu(\fxx)=0$ implies that $Tv(\fxx)=0$ and conclude that $\levelset_0 Tu=\levelset_0 Tv$.
\end{proof}

Corollary 7.9 follows directly from Theorem 7.8.


\begin{corollary}Let $T$ be a contrast-invariant monotone operator on a set $\mathcal F$ of continuous functions $u:\RR^N\to\RR$. Assume that $\mathcal F$ is invariant under continuous contrast changes, and let $\mathcal F_c\subset\mathcal F$ be the functions in $\mathcal F$ whose level sets are compact. Then the set operator $\mathcal T$ defined on the level sets of functions in $\mathcal F_c$  by $\mathcal T \levelset_{\lambda}u=\levelset_1 T\bmone_{\levelset_{\lambda}u}$ satisfies the commutation 
$
\mathcal T \levelset_{\lambda}u=\levelset_{\lambda}Tu 
$ 
for all $\lambda\in\RR$.
\end{corollary}

The next result is based on our discussion in section 6.5 regarding the relation between the continuous functions in $L_C$, which we call continuous $C$-periodic functions, and $C(\mathbb T^N)$, the continuous functions on the $N$-dimensional torus. The main thing to keep in mind is that, although there is a complete correspondence between $C(\mathbb T^N)$ and the continuous $C$-periodic functions on $\RR^N$, the level sets of continuous $C$-periodic functions do not include all of the compact subsets of $C=[-1,1]^N$, but only the ``$C$-periodic'' compact subsets of $C=[-1,1]^N$. These, of course, are in one-to-one correspondence with the compact subsets of $\mathbb T^N$. On the other hand, every compact subset of $[0,1]^N$ appears in its ``symmetrized form'' as a compact subset of $\mathbb T^N$, or equivalently, as a ``$C$-periodic'' compact subset of $C=[-1,1]^N$.

\begin{corollary}
Let $\mathcal F$ be a set of real-valued continuous $C$-periodic functions on $\RR^N$ that is invariant under continuous contrast changes and let $T$ be a contrast-invariant monotone operator defined on $\mathcal F$. Then for all $\lambda\in\RR$, the set operator $\mathcal T$ defined on the level sets of the elements of $\mathcal F$ by the Evans--Spruck extension satisfies the commutation relation
\begin{equation}
\mathcal T\levelset_{\lambda}u=\levelset_{\lambda}Tu.
\end{equation}
\end{corollary}

\section{The extension to upper semicontinuous functions}

We argued in the Introduction that technology is such that digital images can be interpolated to provide a good continuous representations of the original images, and hence that we have at hand continuous images. In practice, the gray levels of these images are quantized and we are left to deal with a finite number of level sets (about 255 with current technology). If we process each level separately, as we wish to do, then we are, in fact, dealing with images that are discontinuous along their quantized level lines. For this reason, it is useful to consider upper semicontinuous functions. These functions arise naturally in our theory if we extend $T$ to a larger class of functions using $\mathcal T$ and superposition (Proposition 6.10). We will see that this extension is necessary in practice; for example, we will need to use it to extend curvature motion to upper semicontinuous functions.

\begin{definition} 
A function $u:\RR^N\to\RR$ is said to be upper semicontinuous (u.s.c.) if either of the following equivalent conditions is true:
\begin{enumerate}[$(i)$]\setlength\itemsep{2pt}
\item The level sets $\levelset_{\lambda}u=\{\fxx\mid u(\fxx)\geq\lambda\}$ are closed.
\item At every $\fxx\in\RR^N$, $\displaystyle{u(\fxx)\geq\limsup_{\fxy\to\fxx}u(\fxy)=\lim_{r\to0}\big(\limsup_{\fxy\in D(\fxx,r)}u(\fxy)\big)}$.
\end{enumerate}
A function $u$ is said to be lower semicontinuous (l.s.c.) if $-u$ is u.s.c.
\end{definition}

\begin{exercise}Show that conditions $(i)$ and $(ii)$ in Definition 7.11 are equivalents and that $u$ is continuous if and only if it is both u.s.c and l.s.c. Prove the following result: If $u$ is u.s.c. and $X$ is compact, then there is a point $\fxx\in X$ such that $u(\fxx)=\sup_{\fxy\in X}u(y)$. What is the corresponding result if $u$ is l.s.c.? \finex
\end{exercise}

\begin{exercise}Show that Definition 7.11 agrees with Definition 3.15 in case $g$ is a nondecreasing real-valued function defined on $\RR$. \finex
\end{exercise}

\begin{exercise}
Let $\mathcal F$ be the set of all u.s.c. functions on $\RR^N$ and let $T_r$, $r>0$, be the operator on $\mathcal F$ defined by $T_r u(\fxx)=\sup_{\fxy\in D(\fxx,r)}u(\fxy)$. Show that $T$ maps $\mathcal F$ into $\mathcal F$ and that the corresponding set operator $\mathcal T_r$ is defined by $\mathcal T_r X= \{\fxx\mid d(\fxx,X)\leq r\}$. $T_r$ is a classic image operator called a \textit{dilation}. \finex
\end{exercise}

The next step in the program is to extend $T$ to a family of upper semicontinuous functions whose level sets are compact. Here is the setting as it has been developed: The contrast-invariant operator $T$ is defined on a set of continuous functions $\mathcal F$. $\mathcal F_c$ is the subset of $\mathcal F$ all of whose level sets are compact. We have extended $T$ to the functions $\bmone_{\levelset_{\lambda}u}$ for $u\in\mathcal F_c$ by defining $T\bmone_{\levelset_{\lambda}u}=\bmone_{\levelset_{\lambda}Tu}$, and thus we have preserved the commutation $\mathcal T{\levelset_{\lambda}u}={\levelset_{\lambda}Tu}$ for all $u\in\mathcal F_c$. We would like to use Proposition 6.10 to extend $T$ to all of the functions $u$ defined by $u(\fxx)=\sup\{\lambda\mid\fxx\in X_\lambda\}$, where $(X_\lambda)_{\lambda\in\RR}$ is a descending chain in $\mathcal L$, the domain of $\mathcal T$. The first problem with this plan is that $\bigcap_{\mu<\lambda}X_\lambda$ may not be in the domain of $\mathcal T$, and thus Proposition 6.10 cannot be used. Another way to look at this is that there may not be enough functions in $\mathcal F_c$ to ensure that $\bigcap_{\mu<\lambda}X_\lambda\in\mathcal L$. The second problem encountered in trying to apply Proposition 6.10 is that $\RR^N$ is not in $\mathcal L$. The way around both of these obstacles is to replace $\RR^N$ with a compact space, and we are going to do this two ways. The first case we have encountered before: We replace $\RR^N$ with $\mathbb T^N$, which is equivalent to considering $C$-periodic functions on $\RR^N$. In this case, to have all of the compact subsets of $\mathbb T^N$, we let $\mathcal F_c$ be all of the continuous functions on $\mathbb T^N$. Then the hypotheses of Proposition 6.10 are fulfilled.

For the other case, we replace $\RR^N$ with its one-point compactification $\RR^{N*}$, and we let $\mathcal F_c$ be all of the continuous functions on $\RR^{N*}$. Then $\RR^N$ is compact in the topology of $\RR^{N*}$, and Proposition 6.10 applies. What we have done here is completely equivalent to letting $\mathcal F_c$ be the set of all continuous functions on $\RR^N$  that tend to a finite limit as $|\fxx|\to+\infty$. In both cases, $\mathcal F_c$ is invariant under continuous contrast changes. The next theorem includes both of these cases. We will prove the theorem for the case the functions are thought of as defined on $\RR^{N*}$. The proof for the other case follows word for word.

\begin{theorem}Assume that $\mathcal F_c$ is either the set of all continuous functions on $\RR^{N}$ that tend to a finite limit as $|\fxx|\to+\infty$ or the set of all continuous $C$-periodic functions on $\RR^N$. Let 
$T$ be a contrast-invariant monotone operator defined on $\mathcal F_c$ and let $\mathcal T$ be its Evans--Spruck extension to $\mathcal L$, the set of all compact subsets of $\RR^{N*}$ (or $\mathbb T^N$). Then $T$ can be extended to a contrast-invariant monotone operator $T^+$ on ${\mathcal F_c}^+$, the set of all upper semicontinuous functions on $\RR^N$ (or upper semicontinuous $C$-periodic functions on $\RR^N$) whose level sets are compact. Furthermore, for $u\in{\mathcal F_c}^+$ and for all $\lambda\in\RR$,
\begin{equation}\label{eq711}
\levelset_{\lambda}T^+u=\mathcal T\levelset_{\lambda}u.
\end{equation}
\end{theorem}

\begin{proof} 
We have argued that Proposition 6.10 applies. This means that there is a contrast-invariant monotone operator $T^+$ defined on ${\mathcal F_c}^+$, since it is clear that the functions $u$ defined by $u(\fxx)=\sup\{\lambda\mid\fxx\in X_\lambda\}$, where $(X_\lambda)_{\lambda\RR}$ is a closed descending chain in $\mathcal L$, are exactly ${\mathcal F_c}^+$, the upper semicontinuous functions on $\RR^{N*}$ whose level sets are compact. If $u\in\mathcal F_c$, then we know from Corollaries 7.9 (and 7.10) that $\mathcal T\levelset_{\lambda}u=\levelset_{\lambda}Tu$, and we have
\[
T^+u(\fxx)=\sup\{\lambda\mid\fxx\in\mathcal T\levelset_{\lambda}u\}=\sup\{\lambda\mid\fxx\in\levelset_{\lambda}Tu\}=Tu(\fxx).
\]
Hence, $T^+$ is indeed a contrast-invariant monotone extension of $T$ from $\mathcal F_c$ to ${\mathcal F_c}^+$.

We must now prove \eqref{eq711}. The simplifications used to prove Theorem 7.8 may be used here, so it is sufficient to prove \eqref{eq711} for $u\leq0$ and $\lambda=0$. Thus we must show that $\levelset_{0}T^+u=\mathcal T\levelset_{0}u$, where $u\in{\mathcal F_c}^+$ and $u\leq0$. In different notation, this is equivalent to proving that $T^+\gamma_{0}(u)=\gamma_{0}(T^+u)$. From Lemma 6.6, $T^+\gamma_{\lambda}(u)\leq\gamma_{\lambda}(T^+u)$ for all $\lambda\in\RR$, or equivalently, $\mathcal T\levelset_{\lambda}u\subset\levelset_{\lambda}T^+u$ for all $\lambda\in\RR$. This reduces the proof to showing that 
\begin{equation}\label{eq712}
\levelset_{0}T^+u\subset\mathcal T\levelset_{0}u.
\end{equation}

The problem here is that we do not know much about the left-hand side of \eqref{eq712}. To get a handle on this, we introduce the distance function $d$ defined by 
\[
d(\fxx)=-d(\fxx,\levelset_{0}u)=-\inf_{\fxy\in\levelset_{0}u}|\fxx-\fxy|,
\]
and to avoid the trivial case, we assume that the compact set $\levelset_{0}u$ is not empty. Clearly, $\levelset_0 u=\levelset_0 d$. The functions $d$ and $u$ satisfy the hypotheses of Lemma 7.7, so we know that there is a continuous contrast change $h$ such that $h(0)=0$ and $d\geq h(u)$. Then $h(u)\in{\mathcal F_c}^+$, and since $T^+$ is monotone and contrast invariant, it is not difficult to see that 
\[
\levelset_{0}T^+u=\levelset_{0}h(T^+u).
\] 
Thus we have
\begin{equation}\label{eq713}
\levelset_{0}T^+u=\levelset_{0}h(T^+u)=\levelset_{0}T^+(h(u))\subset\levelset_{0}T^+d=\levelset_{0}Td.
\end{equation}
On the other hand, we have
\begin{equation}\label{eq714}
\mathcal T\levelset_0 u=\mathcal T\levelset_0 d=\levelset_0 Td,
\end{equation}
and together \eqref{eq713} and \eqref{eq714} prove \eqref{eq712}.
\end{proof}

Recall that in section 6.4 we mentioned in connection with the maxima killer $T_a$ a theory that is dual to the one we have developed. This dual theory is based on lower level sets $\levelset_{\lambda}^- u=\{\fxx\mid u(\fxx)\leq\lambda\}$, whereas the theory we have developed is based on upper level sets $\levelset_{\lambda}^+ u=\levelset_{\lambda} u=\{\fxx\mid u(\fxx)\geq\lambda\}$. The operator $T$ in Theorem 7.12 is defined on all continuous function on $\RR^{N*}$ or on $\mathbb T^N$. This led to a set operator $\mathcal T$ defined on all compact subsets of $\RR^{N*}$ or $\mathbb T^N$. We used $\mathcal T$ to extend $T$ to $T^+$ defined on all functions $u$ of the form  $u(\fxx)=\sup\{\lambda\mid\fxx\in X_\lambda\}$, where $(X_\lambda)_{\lambda\in\RR}$ is a closed descending chain in the domain of $\mathcal T$, that is, a closed descending chain of compact sets. We can also use $\mathcal T$ to extend $T$ to $T^-$ defined on all functions $u$ of the form
\begin{equation}\label{eq715}
u(\fxx)=\inf\{\lambda\mid\fxx\in X_\lambda\},
\end{equation}
where $(X_{-\lambda})_{\lambda\in\RR}$ is the closed descending chain of compact sets that generated the u.s.c. function $-u$. These are the l.s.c.  functions whose lower level sets are compact. Then $T^-$ is defined on the l.s.c. function $u$ by
\begin{equation}\label{eq716}
T^-u(\fxx)=\inf\{\lambda\mid\fxx\in\mathcal T X_\lambda\},
\end{equation}
where  $(X_{-\lambda})_{\lambda\in\RR}$ generated $-u$. We leave it as an exercise to show that $T^-u=-T(-u)$.

\begin{exercise}
Show that defining $T^-$ on l.s.c. functions of the form \eqref{eq715} using \eqref{eq716} is equivalent to defining $T^-$ by $T^-u=-T(-u)$.
\end{exercise}

The duality between upper and lower semicontinuous functions that have, respectively, upper and lower compact level sets, leads immediately to the  dual of Theorem 7.12, which we state as a corollary.

\begin{corollary}With the same hypotheses as Theorem 7.12, $T$ can be extended to a contrast-invariant monotone operator $T^-$ on ${\mathcal F_c}^-$, the set of all lower semicontinuous functions on $\RR^{N*}$ (or $C$-periodic functions on $\RR^N$) whose lower level sets are compact. Furthermore, for $u\in{\mathcal F_c}^-$ and all $\lambda\in\RR$
\[
\levelset_{\lambda}^-T^-u=\mathcal T\levelset_{\lambda}^-u.
\]
\end{corollary}

\begin{exercise}Let $T$ be a contrast-invariant monotone operator defined on $\mathcal F$. Assume that $u\in\mathcal F$ implies that $\bmone_{\levelset_{\lambda}u}\in\mathcal F$ and that $\mathcal F$ is invariant under upper semicontinuous contrast changes. Prove that if $T$ commutes with all thresholds, that is, if $T\gamma_\lambda(u)=\gamma_\lambda(Tu)$ for all $\lambda\in\RR$, then $Tg(u)=g(Tu)$ for all upper semicontinuous contrast changes $g$. Hint: Show that $Tg(u)$ and $g(Tu)$ have the same level sets. For this, it is a notational convenience to introduce the associated set operator $\mathcal T$. \finex
\end{exercise}

Figure 7.1 illustrates a common problem in vision. Looking at the chessboard we ask, Are there black squares on a white background or are there white squares on a black background? Saying that the background is white means that the white area is connected and closed. If black is coded with zero and white is coded with 255, then this means that the image is being interpreted as being upper semicontinuous. If we interpret the image as being white squares on a black background, then we are interpreting it as a lower semicontinuous image. If we interpret it as being u.s.c. and apply $T^+$, we get one result. We get a quite different result if we make the other interpretation and apply $T^-$. 

\begin{figure}[!t]
\setkeys{Gin}{width=3cm}
\centerline{
\includegraphics{fig07.01.1.eps}
\includegraphics{fig07.01.2.eps}
\includegraphics{fig07.01.3.eps}
\includegraphics{fig07.01.4.eps}
}
\caption[Evans-Spruck extensions and the chessboard dilemma]
{The chessboard dilemma. Left: a chessboard image. Next: result with the finite difference scheme for the curvature motion, applied up to a fixed scale (Chapter 23). The creation of a new gray level proves that the scheme is not fully contrast invariant. Indeed, by Proposition 6.3, a contrast-invariant operator does not create new levels. The observed new gray level corresponds to an average of the original ones. The next two images are obtained by the Evans--Spruck extension of the curvature motion, first under the assumption that the image is u.s.c. and second under the assumption that it is l.s.c. The schemes are fully contrast invariant in both cases and are extensions of the curvature motion as specified in Theorem 7.12 and Corollary 7.13.}
\end{figure}

\section{A Who's Who of monotone operators}

We wish to summarize the main results about monotone function and set operators that have been developed beginning in Chapter 3 and continuing through Chapter 6 and the present chapter, and we would like to do this in a  compact graphic style that can be used as a reference. With this in mind, we abbreviate the often-appearing phrase ``almost everywhere, except possibly for at most a countable number of $\lambda$'s'' by writing ``aeec$\lambda$'s.'' All of the function and set operators are assumed to be monotone. The domain of $T$ is denoted by $\mathcal F$ and the domain of $\mathcal T$ is denoted by $\mathcal L$. Recall also that an assumption about $T$ or $\mathcal T$ entails the related assumption about its domain of definition.

As we have tried to do in elsewhere, we focus either on a function operator $T$ or on a set operator $\mathcal T$, which is another way of saying that we begin with $T$ or we begin with $\mathcal T$. This reflects what happens in practice. It is often easier and more intuitive to define an image operator as a set operator. We have already encountered this in the extrema killer, and this will be the case when we introduce the median filter; there will be other examples. Other image operators appear first as differential operators on a set of continuous functions. This is the case, for example, of the curvature motion. In this setting, we go from a function operator $T$ on continuous functions to a set operator $\mathcal T$ on compact sets. The theory we have developed gives us the freedom to move between $(T,\mathcal F)$ and $(\mathcal T,\mathcal L)$. 

\paragraph*{Case 1: Given a set operator $\mathcal T$ defined on $\mathcal L$.}\leavevmode

\bigskip
\noindent
\begin{minipage}{\textwidth}
\parbox[t]{5.3cm}{{${A_{\mathcal T}}$ (Basic assumptions):}\\
$\RR^N, \emptyset \in\mathcal L$. $(X_\lambda)_{\lambda\in\RR}\in\mathcal L$\\ implies  
$\bigcap_{\mu<\lambda}X_\mu\in\mathcal L$.\\ 
$\mathcal T\emptyset=\emptyset$, $\mathcal T\RR^N=\RR^N$.
}\hfill$\stackrel{\text{Prop. 6.10}}{\Longrightarrow}$\hfill
\parbox[t]{5.3cm}{\raggedright$Tu(\fxx):=\sup\{\lambda\mid\fxx\in\mathcal T X_\lambda\}$, 
where $(X_\lambda)_{\lambda\in\RR}$ generates $u$. 
$T$ is contrast invariant.
$\mathcal T\levelset_{\lambda}u=\levelset_{\lambda}Tu$ aeec$\lambda$'s.
}
\end{minipage}

\bigskip

\noindent
\begin{minipage}{\textwidth}
\parbox[t]{5.3cm}{$A_{\mathcal T}$ plus $\mathcal T$ u.s.c. on $\mathcal L$.}
\hfill$\stackrel{\text{Thm. 6.12}}{\Longrightarrow}$\hfill
\parbox[t]{5.3cm}{\raggedright$\mathcal T\levelset_{\lambda}u=\levelset_{\lambda}Tu$ for all $\lambda\in\RR$.}
\end{minipage}


\bigskip

\noindent
\begin{minipage}{\textwidth}
\parbox[t]{5.3cm}{$A_{\mathcal T}$ plus $\mathcal T$ translation invariant.}
\hfill$\stackrel{\text{Thm. 7.1}}{\Longrightarrow}$\hfill
\parbox[t]{5.3cm}{\raggedright$\mathcal T X
=\{\fxx\mid\exists B\in\mathcal B : \fxx+B\subset X \}$, $\mathcal B:=\{X\mid 0\in\mathcal T X, X\in\mathcal L\}$.}
\end{minipage}

\paragraph*{Case 2: Given a function operator $T$ defined on $\mathcal F$.}\leavevmode

\bigskip
\noindent
\begin{minipage}{\textwidth}
\parbox[t]{5.3cm}{\raggedright$A_{T}$ (Basic assumptions):\\
$u\in\mathcal F$ implies $\bmone_{\levelset_{\lambda}}u\in\mathcal F$. $T$ contrast invariant with respect to $\mathcal G_{Lip}$.  
}
\hfill$\stackrel{\text{Prop 6.8}}{\Longrightarrow}$\hfill
\parbox[t]{5.3cm}{\raggedright$Tu(\fxx)=\sup\{\lambda\mid\fxx\in\mathcal T\levelset_{\lambda}u\}$ a.e., $\mathcal T\levelset_{\lambda}u :=\levelset_1 T\bmone_{\levelset_{\lambda}u}$, $\mathcal L:=\{\levelset_{\lambda}u\}$.
$\mathcal T\levelset_{\lambda}u=\levelset_{\lambda}Tu$ aeec$\lambda$'s.\\ $\mathcal T$ satisfies $A_{\mathcal T}$.}
\end{minipage}

\bigskip

\noindent
\begin{minipage}{\textwidth}
\parbox[t]{5.3cm}{$A_{T}$ plus $T\bmone_{\levelset_{\lambda}u}=\bmone_{\levelset_{\lambda}Tu}$.}
\hfill$\stackrel{\text{Thm. 6.12}}{\Longrightarrow}$\hfill
\parbox[t]{5.3cm}{\raggedright The results above hold for all $\fxx\in\RR^N$ and all $\lambda\in\RR$.}
\end{minipage}


\bigskip

\noindent
\begin{minipage}{\textwidth}
\parbox[t]{5.3cm}{$A_{T}$}
\hfill$\stackrel{\text{Thm. 7.3}}{\Longrightarrow}$\hfill
\parbox[t]{5.3cm}{\raggedright$Tu(\fxx)=\sup_{B\in{\mathcal B}_{\fxx}}\inf_{\fxy\in B}u(\fxy)$ a.e., $\mathcal B_{\fxx}:=\{X\mid \fxx\in\mathcal T X, X\in\mathcal L\}$.}
\end{minipage}

\bigskip

\noindent
\begin{minipage}{\textwidth}
\parbox[t]{5.3cm}{$A_{T}$ plus $T$ translation invariant.}
\hfill$\stackrel{\text{Thm. 7.3}}{\Longrightarrow}$\hfill
\parbox[t]{5.3cm}{\raggedright$Tu(\fxx)=\sup_{B\in{\mathcal B}_{0}}\inf_{\fxy\in B}u(\fxy)$ a.e., $\mathcal B_{0}:=\{X\mid 0\in\mathcal T X, X\in\mathcal L\}$.}
\end{minipage}


\paragraph*{Case 3: Given a set $\mathcal B\subset\mathcal P(\RR^N)$.}\leavevmode

\bigskip
\noindent
\begin{minipage}{\textwidth}
\parbox[t]{5.3cm}{$D_{\mathcal T}$ (Definition):\\
$\mathcal T X:=\{\fxx\mid\exists B\in\mathcal B : \fxx+B\subset X \}$}
\hfill$\stackrel{\text{Thm. 7.1}}{\Longrightarrow}$\hfill
\parbox[t]{5.3cm}{\raggedright$\mathcal T$ monotone and translation invariant on $\mathcal P(\RR^N)$.}
\end{minipage}

\bigskip
\noindent
\begin{minipage}{\textwidth}
\parbox[t]{5.3cm}{$D_{T}$ (Definition):\\
$Tu(\fxx)=\sup_{B\in{\fxx+\mathcal B}}\inf_{\fxy\in B}u(\fxy)$}
\hfill$\stackrel{\text{Thm. 7.3}}{\Longrightarrow}$\hfill
\parbox[t]{5.3cm}{\raggedright$T$ monotone, translation and contrast invariant on $u:\RR^N\to\RR$.}
\end{minipage}

\bigskip
\noindent
\begin{minipage}{\textwidth}
\parbox[t]{5.3cm}{$D_{\mathcal T}$ plus condition in Prop. 7.2.
}
\hfill$\stackrel{\text{Prop. 7.2}}{\Longrightarrow}$\hfill
\parbox[t]{5.3cm}{\raggedright$\mathcal T$ u.s.c. on $\mathcal L$.}
\end{minipage}


\paragraph*{Case 4: Given $T$ defined on the continuous functions on $\mathbb T^N$ or $\RR^{N*}$.}\leavevmode

$T$ can be extended uniquely to the functions $\bmone_X$ where $X$ is any  compact subset of $\mathbb T^N$ or $\RR^{N*}$ (Theorem 7.8, Evans--Spruck). The set operator $\mathcal T$ defined by $\mathcal T X=\levelset_1 T\bmone_X$ can be used to extend $T$ to all upper semicontinuous functions on $\mathbb T^N$ or $\RR^{N*}$ that have compact level sets. Each of these extensions preserves commutation.

\section{Comments and references}

The formalism presented in this chapter is due to Matheron \cite{Matheron:1975:RSI} in the case of set operators and to Serra \cite{Serra:1982:IAM} and Maragos \cite{Maragos:1989:RTM} in the case of function operators. Serra's formalism is actually more general than the one presented here; it will be developed in Chapter 15, which is about ``nonflat'' morphology. Our presentation relating the sup-inf form of the operator directly to contrast invariance and establishing the full equivalence between sup-inf operators and contrast-invariant monotone operators is original. The mysterious ``set of structuring elements'' has received a great deal of attention in the literature. Here are a few references: on finding the right set of structuring elements \cite{Salembier:1992:SEA,Svalbe:1992:DMF}; on simplifying them \cite{Schonfeld:1994:OSE}; on decomposing them into simpler ones as one does with linear filters \cite{Park:1995:DAS,Zhuang:1994:DMS,Zhuang:1986:MSE}; on reducing the number \cite{Richardson:1991:LBS}.

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









 