%gmChap03.tex

%\graphicspath{{./figures/chapter03/}}


\begin{slide}
\section{From an image to its level sets and back}

$\barR=\RR\cup\{-\infty,+\infty\}$.


\begin{definition}
Let $u$ be a function defined on $\RR^N$ with values in $\barR$. The level set of $u$ at level $\lambda$ is denoted by $\levelset_{\lambda}u$ and defined by
\[
\levelset_{\lambda}u=\{\fxx\mid u(\fxx)\geq\lambda\}.
\]
\end{definition}


We can reconstruct $u$ from its level sets $\levelset_{\lambda}u$
by the formula
\[
u(\fxx)=\sup\{\lambda\mid\fxx\in\levelset_{\lambda}u,\lambda\in\barR\}.
\]


If a contrast change $g:\barR\to\barR$ is continuous and
increasing. Then   $v=g(u)$ and $u$ have the same level sets
globally, that is, every level set of $u$ is a level set of $v$,
and conversely.
\end{slide}

\begin{figure}[!t]
\setkeys{Gin}{width=2.5cm} \centerline{
\includegraphics{fig03.01.1.eps}
\includegraphics{fig03.01.2.eps}
\includegraphics{fig03.01.3.eps}
}
\centerline{
\includegraphics{fig03.01.4.eps}
\includegraphics{fig03.01.5.eps}
\includegraphics{fig03.01.6.eps}
}
\centerline{
\includegraphics{fig03.01.7.eps}
\includegraphics{fig03.01.8.eps}
\includegraphics{fig03.01.9.eps}
}
\caption[Level sets of a digital image]{\label{fig31} Level sets of a digital image. Left to right, top to bottom: We first show an image with range of gray levels from 0 to 255. Then we show eight level sets in decreasing order from $\lambda=225$ to $\lambda=50$, where the grayscale step is 25. Notice how essential features of the shapes are contained in the boundaries of level sets, the level lines. Each level set (which appears as white) is contained in the next one, as guaranteed by Proposition 3.2.}
\end{figure}

\begin{slide}
\begin{proposition}\label{prop32}
Let $X_{\lambda}$, be the level  sets $\levelset_{\lambda}u$ of a
function $u$. Then
\begin{enumerate}%[$(i)$]\setlength\itemsep{2pt}
\item If $\lambda>\mu$, then $X_{\lambda}\subset X_{\mu}$, and $X_{-\infty}=\RR^N$.
\item $X_{\lambda}=\bigcap_{\mu<\lambda}X_{\mu}$ for every $\lambda>-\infty$.
\end{enumerate}
Conversely, if $(X_{\lambda})_{\lambda\in\barR}$  is a family of
subsets of $\RR^N$ that satisfies $1)$, and $2)$, then the level
sets of the function $u$ defined by
\begin{equation}\label{eq31}
u(\fxx)=\sup\{\lambda\mid \fxx\in X_{\mu},\lambda\in\barR\}
\end{equation}
satisfy
\begin{equation}\label{eq32}
X_{\lambda}=\levelset_{\lambda}u
\end{equation}
\end{proposition}

\end{slide}

\begin{slide}
{\Large Proof} $X_\lambda=\levelset_\lambda  u$.
\newline
(1) If $\lambda>\mu$, then $X_{\lambda}\subset X_{\mu}$, and
$X_{-\infty}=\RR^N$. \newline (2)
$X_{\lambda}=\bigcap_{\mu<\lambda}X_{\mu}$ for every
$\lambda>-\infty$.
\newline

Relation $(1)$ follows directly from the definition of
$\levelset_\lambda u$.
\newline Relation $(2)$ follows from
$u(\fxx)\geq\lambda $ iff $ u(\fxx)\geq\mu$ for every
$\mu<\lambda$.
\newline
Conversely, assume that a family of subsets
$(X_{\lambda})_{\lambda\in\barR}$  satisfies $(1)$ and $(2)$. Let
$u(\fxx)=\sup\{\lambda\mid \fxx\in X_{\mu},\lambda\in\barR\}$
Suppose that $\fxx\in X_{\lambda}$. By definition of $u$,
$u(\fxx)\geq\lambda$, and hence $\fxx\in\levelset_{\lambda}u$.
Thus, $X_{\lambda}\subset\levelset_{\lambda}u$.

\medskip Assume now that $\fxx\in\levelset_{\lambda}u$.
Then $u(\fxx)=\sup\{\nu\mid \fxx\in X_{\nu}\}\geq\lambda$.
Consider any $\mu<\lambda$. Then there exists a $\mu'$ such that
$\mu<\mu'\leq \sup\{\nu\mid \fxx\in X_{\nu}\}$ and $\fxx\in
X_{\mu'}$. It follows from $(1)$ that $\fxx\in X_{\mu}$. Since
$\mu<\lambda$ was arbitrary,  we get
$\fxx\in\bigcap_{\mu<\lambda}X_{\mu}=X_\lambda$.

\end{slide}

\begin{slide}

\begin{definition}\label{chains}
\begin{enumerate}%[$(i)$]\setlength\itemsep{2pt}
\item If $\lambda>\mu$, then $X_{\lambda}\subset X_{\mu}$, and
$X_{-\infty}=\RR^N$. \item
$X_{\lambda}=\bigcap_{\mu<\lambda}X_{\mu}$ for every
$\lambda>-\infty$.
\end{enumerate}
A family of subsets  $(X_\lambda)_{\lambda\in\barR}$ of $\RR^N$
that satisfies condition $1.$  is called nonincreasing; it is
called closed  nonincreasing if it also satisfies condition $2.$.
\end{definition}
\end{slide}

\begin{figure}[!t]
\setkeys{Gin}{width=2.5cm}
\centerline{
\framebox{\includegraphics{fig03.02.1.eps}}
\framebox{\includegraphics{fig03.02.2.eps}}
\framebox{\includegraphics{fig03.02.3.eps}}
\framebox{\includegraphics{fig03.02.4.eps}}
}
\vspace{1.5pt}
\centerline{\hspace{2.84cm}
\framebox{\includegraphics{fig03.02.5.eps}}
\framebox{\includegraphics{fig03.02.6.eps}}
\framebox{\includegraphics{fig03.02.7.eps}}
}
\caption[Level sets of a simple synthetic image]{\label{fig32}
A simple synthetic image and all of its level sets (in white) with  decreasing levels, from left to right and from top to bottom.}
\end{figure}









\begin{figure}[!t]
\setkeys{Gin}{width=8cm} \centerline{
\includegraphics{fig03.03.1.eps}
}
\caption[Reconstruction of an image from its level sets]{\label{fig33}  Reconstruction of an image from its level sets: an illustration of  Proposition 3.2.  We use four different subsets of the image's level sets to give four reconstructions. Top, left: all level sets;  top, right: all level sets whose gray level is a multiple of 8; bottom, left: multiples of 16;   bottom, right: multiples of 32. Notice the relative stability of the image shape content under these drastic quantizations of the gray levels.
}
\end{figure}



\begin{slide}

\subsection{Functions and level sets defined almost everywhere}



\begin{lemma}\label{lem35}
Assume that $(X_{\lambda})_{\lambda\in\RR}$  is a nonincreasing
family of measurable sets. Then,
\begin{equation}\label{eq35}
X_{\lambda}=\bigcap_{\mu<\lambda}X_{\mu}
\end{equation}
almost everywhere, with the possible  exception of at most a
countable number of $\lambda's$,
\end{lemma}

 {\Large Proof}
Let $h$ be the Gauss function $G_1$. Write $m(X)=\int_X
h(\fxx)\,\rmd\fxx$. The function $\lambda\mapsto m(X_{\lambda})$
is nonincreasing. Thus, it is continuous except possibly for a
countable number of points where it ``jumps.'' Call this
exceptional set $\Lambda$. Then
$\lim_{\mu\to\lambda}m(X_{\mu})=m(X_{\lambda})$ for
$\lambda\in\RR\setminus\Lambda$. Thus $m(X_{\mu})\downarrow
m(\bigcap_{\mu<\lambda}X_{\mu})$ as $\mu\uparrow\lambda$. Thus,
$m(\bigcap_{\mu<\lambda}X_{\mu})=m(X_{\lambda})$. Since
$X_{\lambda}\subset\bigcap_{\mu<\lambda}X_{\mu}$, this means that
$m(\bigcap_{\mu<\lambda}X_{\mu}\setminus X_{\lambda})=0$, which
implies \eqref{eq35}.
\end{slide}



There is  a one-to-one correspondence between the points
$\lambda\in\barR$ where the function $\lambda\mapsto m(X_\lambda)$
is discontinuous and the sets $\{\fxx\mid u(\fxx)=\lambda\}$ that
have positive measure.


\begin{corollary}
Let $(X_\lambda)_{\lambda\in \barR}$ be a nondecreasing family in
$\RR^N$ and define $u:\RR^N\to\barR$ by
\[
u(\fxx) =  \sup\{\lambda\mid\fxx \in X_\lambda \}.
\]
Then   $X_{\lambda} = \levelset_{\lambda} u$ almost everywhere,
except possibly for at most a countable number of $\lambda's$.
\end{corollary}









\begin{slide}
\section{Contrast changes and level sets}

\begin{definition}
Any nondecreasing function $g:\RR\to\RR$ will be called a contrast
change.
\end{definition}


\begin{definition}
The pseudoinverse of any contrast change $g:\barR\to\barR$ is defined by
\[
g^{(-1)}(\lambda)=\inf \{r\mid g(r)\geq\lambda\}.
\]
\end{definition}


\begin{exercise}
Compute $g^{(-1)}$ for the following functions.
\begin{enumerate}%[(i)]\setlength\itemsep{2pt}
\item $g(s)=\max(0,s)$.
\item $g(s)=1$ if $s\geq0$, and $g(s)=0$ if $s<0$. \finex
\end{enumerate}
\end{exercise}
\end{slide}

\begin{figure}[!t]
\setkeys{Gin}{width=10cm}
\centerline{
\includegraphics{fig03.04.1.eps}
}
\caption[Histogram of an image]{\label{fig34}The histogram of the image Bird. For each $i \in \{0, 1,\ldots, 255\}$, we display (above, right) the function $h(i) = \text{Card}\,\{\fxx\mid u(\fxx)=i\}$. The function below is the is given by $g(i) = \text{Card}\,\{\fxx\mid u(\fxx) \leq i \}$, an integral of $h$. It provides an indication about the overall contrast of the image and about the contrast change imposed by the sensors. The inverse function $g^{-1}$ can be used as a contrast change to create an image $g^{-1}(u)$ with a flat histogram.}
\end{figure}



\begin{slide}
\begin{lemma}
Suppose that $g:\barR\to\barR$ is a contrast change. Then for
$\lambda\in\barR$, we have the following two properties:
\begin{equation}\label{eq36}
\text{If } \lambda\leq g(g^{(-1)}(\lambda)), \text{ then }
g(s)\geq\lambda\text{ if and only if } s\geq g^{(-1)}(\lambda).
\end{equation}
\begin{equation}\label{eq37}
\text{If } \lambda>g(g^{(-1)}(\lambda)), \text{ then }
g(s)\geq\lambda\text{ if and only if } s> g^{(-1)}(\lambda).
\end{equation}
\end{lemma}


\begin{theorem}
Let $u$ be a real-valued function defined on $\RR^N$ and let $g$ be a contrast change. Then for $\lambda\in\barR$, the level set $\levelset_{\lambda}g(u)$ satisfies one of the following relations:\newline
\noindent Either
\vspace{-8pt}
\begin{align}
\levelset_{\lambda}g(u)&= \{\fxx\mid u(\fxx)\geq g^{(-1)}(\lambda)\}
= \levelset_{g^{(-1)}(\lambda)}u,\\[-3ex]
\intertext{or}\notag\\[-6ex]
\levelset_{\lambda}g(u)&= \{\fxx\mid u(\fxx)> g^{(-1)}(\lambda)\}
= \bigcup_{\mu>g^{(-1)}(\lambda)}\levelset_{\mu}u.
\end{align}
\end{theorem}

\end{slide}


\begin{figure}[!t]
\setkeys{Gin}{width=5cm} \centerline{
\includegraphics{fig03.05.1.eps}
}
\caption[Contrast changes and an equivalence class of images]{\label{fig35}Contrast changes and an equivalence class of images. The three images have exactly the same level sets and level lines, but their level sets are mapped onto three different gray-level scales. The graphs on the right are the graphs of the contrast changes $u\mapsto g(u)$ that have been applied to the initial gray levels. The first one is concave; it enhances the darker parts of the image. The second one is the identity; it leaves the image unaltered. The third one is convex; it enhances the brighter parts of the image. Software allows one to manipulate the contrast of an image to obtain the best visualization. From the image analysis viewpoint, image data should be considered as an equivalence class under all possible contrast changes.}
\end{figure}
\begin{slide}

{\Large Remark} Let $u:\RR^N\to\RR$ be measurable and let $g$ be a
contrast change. Then for $\lambda\in\RR$ and $\varepsilon>0$,
there exists a $\mu\in\RR$ such that
$\levelset_{\mu}u\subset\levelset_{\lambda}g(u)$ and
$\text{meas}\,(\levelset_{\lambda}g(u)\setminus\levelset_{\mu}u)<\varepsilon$.


\end{slide}


\begin{figure}[!t]
\setkeys{Gin}{width=10cm}
\centerline{
\includegraphics{fig03.06.1.eps}
}
\caption[Histogram and contrast change II]{\label{fig36} The two images (left) have the same set of level sets. The contrast change that maps the upper image onto the lower image is displayed on the right. It corresponds to one of the possible $g$ functions whose existence is stated in Corollary 3.14. The function $g$ may be locally constant on intervals where the histogram of the upper image is zero (see top, middle graph). Indeed, on such intervals, the level sets are invariant.
}
\end{figure}

\begin{slide}

\begin{theorem}
Suppose that $u$ and $v$ are two real-valued functions defined on $\RR^N$ such that for every $\lambda\in\barR$ the following alternative holds:\newline
\noindent Either there exists a $\mu\in\barR$ such that
%\vspace{-8pt}
\begin{align}
\levelset_{\lambda}v&=\{\fxx\mid u(\fxx)\geq \mu\}=\levelset_{\mu}u,\\
\intertext{or there exists a $\mu\in\barR$ such that}
\levelset_{\lambda}v&=\{\fxx\mid u(\fxx)> \mu\}=\bigcup_{\nu>\mu}\levelset_{\nu}u.
\end{align}
Then the contrast change $g:\barR\to\barR$ defined by
\begin{equation}\label{ex}
g(\mu)=\sup\{\lambda\mid\levelset_{\mu}u\subset\levelset_{\lambda}v\}
\end{equation}
maps $u$ onto $v$, that is, $v=g(u)$.
\end{theorem}

\end{slide}





\begin{slide}
\begin{corollary}
If $u$ and $v$ are two real-valued functions such that all the level sets of $v$ are level sets of $u$, then the contrast change $g:\barR\to\barR$ defined by
\begin{equation}
g(\mu)=\sup\{\lambda\mid\levelset_{\mu}u\subset\levelset_{\lambda}v\}
\end{equation}
maps $u$ onto $v$.
\end{corollary}


\end{slide}
\begin{figure}[!t]
\setkeys{Gin}{width=12cm}
\centerline{
\includegraphics{fig03.07.1.eps}
}
\caption[Histogram  contrast change I]{\label{fig37}The original image (top, left) has a strictly positive histogram (all gray levels between 0 and 255 are represented). Therefore, if any contrast change $g$ that is not strictly increasing is applied, then some data will be lost. Every level set of the transformed image $g(u)$ is a level set of the original image; however, the original image has more level sets than the transformed image.
}
\end{figure}
