
 \graphicspath{{./figures/}}


%\addcontentsline{toc}{chapter}{Introduction} \markboth{Introduction}{Introduction}

\renewcommand{\thesection}{{I}.\arabic{section}}
\renewcommand{\thefigure}{{I}.\arabic{figure}}
\renewcommand{\theequation}{{I}.\arabic{equation}}






\chapter{Notation and background material\label{sectionI.4}}



$\mathbb R^N$ denotes the real $N$-dimensional Euclidian space. If ${\bf x} \in\mathbb R^N$ and $N>2$, we write ${\bm
x}=(x_1,x_2,\ldots,x_N)$; if $N=2$, we usually write ${\bm x}=(x,y)$. For ${\bm x},\, {\bm y}\in\mathbb R^N$, we denote
their scalar product by ${\bm x}\cdot{\bm y}=x_1y_1+x_2y_2+\cdots+x_Ny_N$ and write $$|{\bm x}|=({\bm x}\cdot{\bm
x})^{1/2}=(x_1^2+x_2^2+\cdots+x_N^2)^{1/2}.$$


Let $\Omega$ be an open set in $\mathbb R^N$, and let $n\in\mathbb N$ be a fixed integer. $C^n(\Omega)$ denotes the set
of real-valued functions $f:\Omega\to\mathbb R$ that have  bounded continuous derivatives of all orders up to and
including $n$. $f\in C^{\infty}(\Omega)$ means that $f$ has continuous derivatives of all orders and that they are all
bounded; $f\in C(\Omega)=C^0(\Omega)$ means that $f$ is continuous and bounded on $\Omega$. We will often write ``$f$
is $C^n$'' as shorthand for $f\in C^n(\Omega)$, and we often omit the domain $\Omega$ if there is no chance of
confusion.

We use multi-indices of the form $\alpha=(\alpha_1,\alpha_2,\ldots,\alpha_N)\in{\mathbb N}^N$ as shorthand in several
cases. For ${\bm x}\in{\mathbb R}^N$, we write ${\bm x}^{\alpha}$ and $|{\bm x}|^{\alpha}$ for
$x_1^{\alpha_1}x_2^{\alpha_2}\cdots x_N^{\alpha_N}$ and $|x_1|^{\alpha_1}|x_2|^{\alpha_2}\cdots |x_N|^{\alpha_N}$,
respectively. For $f\in C^n(\Omega)$, we abbreviate the partial derivatives of $f$ by writing
\[
\partial^\alpha f= \frac{\partial^{|\alpha|}f}{\partial x_1^{\alpha_1}\partial x_2^{\alpha_2}\cdots\partial x_N^{\alpha_N}},
\]
where $|\alpha|=\alpha_1+\alpha_2+\cdots+\alpha_N$ and $|\alpha|\leq n$.

We also write the partial derivatives of $f({\bm x})=f(x_1,x_2,\ldots,x_N)$ as $f_i=\partial f/\partial x_i$,
$f_{ij}=\partial^2 f/\partial x_i\partial x_j$, and so on. In the two-dimensional case $f({\bm x})=f(x,y)$, we usually
write $\partial f/\partial x=f_x$, $\partial f/\partial y=f_y$, $\partial^2 f/\partial x\partial y =f_{xy}$, and so on.

The gradient of $f$ is denoted by $Df$. Thus, if $f({\bm x})=f(x_1,x_2,\ldots,x_N)$,
\[
Df=(f_1,f_2,\ldots,f_N),
\]
and
\[
Df=(f_x,f_y)
\]
in case $N=2$. The Laplacian of $f$ is denoted by $\Delta f$. Thus $\Delta f=f_{11}+f_{22}+\cdots+f_{NN}$ in general,
and $\Delta f=f_{xx}+f_{yy}$ if $N=2$.

We will often use the symbols $O$, $o$, and $\varepsilon$. They are defined as follows. We assume that $h$ is a real
variable that tends to a limit $h_0$ that can be finite or infinite. We assume that $g$ is a positive function of $h$
and that $f$ is any other function of $h$. Then $f=O(g)$ means that there is a constant $C>0$ such that $|f(h)|<Cg(h)$
for all values of $h$. The expression $f=o(g)$ means that $f(h)/g(h)\to 0$ as $h\to h_0$. We occasionally will use
$\varepsilon$ to denote a function of $h$ that tends to zero as $h\to 0$. Thus, $f(h)=o(h)$ can be written equivalently
as $f(h)=h\varepsilon(h)$.

\subsection*{Taylor's formula}

\hspace*{0pt}{\indent} An $N$-dimensional form of Taylor's formula is used several times in the book. We will first
state it and then explain the notation. Assume that $f\in C^n(\Omega)$ for some open set $\Omega\in\mathbb R^N$, that
${\bm x}, {\bm y}\in\Omega$, and that the segment joining ${\bm x}$ and ${\bm x}+{\bm y}$ is also in $\Omega$. Then
\[
f({\bm x}+{\bm y})=f({\bm x})+\frac{1}{1!}Df({\bm x}){\bm y}^{(1)}+\frac{1}{2!}D^2f({\bm x}){\bm
y}^{(2)}+\cdots+\frac{1}{n!}D^n f({\bm x}){\bm y}^{(n)}+o(|{\bm y}|^n).
\]

This has been written compactly to resemble the one-dimensional case, but the price to be paid is to explain the
meaning of $D^p f({\bm x}){\bm y}^{(p)}$. We have already seen special cases of this expression in section {\sc I}.3,
for example, $D^2u(Du,Du)$ in equation ({\sc I}.4). The expression $D^p f({\bm x}){\bm y}^{(p)}$ is
\[
D^pf({\bm x}){\bm y}^{(p)}=D^p f({\bm x})(\underbrace{\bm y,\bm y,\ldots,\bm y}_{\text{$p$
terms}})=\sum_{(i_1,i_2,\ldots,i_p)}\frac{\partial^p f}{\partial x_{i_1}\partial x_{i_2}\cdots\partial
x_{i_p}}(\fxx)y_{i_1}y_{i_2}\cdots y_{i_p},
\]
where the sum is taken over all $N^p$ different vectors $(i_1,i_2,\ldots,i_p)$, $i_j=1,2,\ldots,N$. Notice that
$Df({\bm x}){\bm y}^{(1)}$ is just $\sum_{j=1}^N f_{j}y_j=Df({\bm x})\cdot{\bm y}$, which is how we usually write it.

The so-called Lagrange variant of Taylor's formula will be equally useful, \begin{equation}\label{TaylorLagrange}
f({\bm x}+{\bm y})=f({\bm x})+\cdots+\frac{1}{(n-1)!}D^{n-1} f({\bm x}){\bm y}^{(n-1)}+\frac{1}{n!}D^n f({\bm
x+\theta\fxy}){\bm y}^{(n)},
\end{equation}
where $\theta=\theta(\fxy)$  ranges in $[0,1]$.

\subsection*{The implicit function theorem}

\hspace*{0pt}{\indent}Consider a real-valued $C^1$ function $f$ defined on an open set $\Omega$ in $\RR^N$. For ease of
notation we write $\fxz=(\fxx,y)$, where $\fxx=(x_1,\ldots,x_{N-1})$ and $y=x_N$. Assume that $f(\fxz_0)=0$ for a point
$\fxz_0\in\Omega$ and that $f_y(\fxx_0)\ne0$. Then there is a neighborhood $M=M(\fxx_0)$ and a neighborhood $N=N(y_0)$
such that for every $\fxx\in M$ there is exactly one $y\in N$ such that $f(\fxx,y)=0$. The function $y=\varphi(\fxx)$
is $C^1$ on $M$ and $y_0=\varphi(\fxx_0)$. Furthermore, if $f\in C^n(\Omega)$, then $\varphi\in C^n(M)$.

\subsection*{Lebesgue integration}

\hspace*{0pt}{\indent}The Lebesgue integral, which first appeared in 1901 and is thus over a hundred years old, has
become the workhorse of analysis. It plays  a   role in chapters 1 and 2 and appears briefly in other parts of the
book. One does not need a profound understanding of abstract measure theory and integration to follow the arguments.
One should, however, be familiar with a few key results and be comfortable with the basic manipulations of the
integral. With this in mind, we restate some of these fundamentals.

The functions and sets in this book are always measurable.
 Thus we dispense in general with phrases like ``let $f$ be
 a measurable function.''  We denote by $\mathcal M$  the set of
 Lebesgue  measurable subsets of $\RR^N$.  Since we shall sometimes
 need to complete $\RR^N$ by a point at infinity, $\infty$, we still denote
 by $\mathcal M$ the measurable sets of $\SN=\RR^N\cup\{\infty\}$ and
 take $\hbox{measure}(\{\infty\})=0$.  A function $f$ defined on
  a subset $A$ of $\mathbb R^N$ is integrable, if
\[
\int_A|f({\bm x})|\,{\rm d}{\bm x}<+\infty.
\]
The Banach space of all integrable function defined on $A$ is denoted as usual by $L^1(A)$; we write
$\|f\|_{L^1(A)}=\int_A|f({\bm x})|\,\rm d\bm x$ to denote the norm of $f$ in $L^1(A)$. The most important applications
in the book are the two cases $A=\mathbb R^N$ and $A=[-1,1]^N$. Here are two results that we use in chapters 1 and 2.
We state them not in the most  general form, but rather in the simplest form suitable for our work.

\subsection*{A density theorem for $L^1(\mathbb R^N)$}

\hspace*{0pt}{\indent}If $f$ is in $L^1(\mathbb R^N)$, then there exists a sequence of continuous functions $\{g_n\}$,
each of which has compact support, such that $g_n\to f$ in  $L^1(\mathbb R^N)$, that is,
$\int|g_n(\fxx)-f(\fxx)|d\fxx\to 0$ as $n\to+\infty$. This result is true for $L^1([-1,1]^N)$, in which case the $g_n$
are continuous on $[-1,1]^N$.

\subsection*{Fubini's theorem}

\hspace*{0pt}{\indent}Suppose that $f$ is a measurable function defined on $A\times B\in\mathbb R^N\times\RR^N$.
Fubini's theorem states that
\[
\int_{A\times B}|f(\fxz)|\,{\rm d}{\bm z}=\int_{A}\int_{B}|f(\fxx,\fxy)|\,{\rm d}\fxx\,{\rm
d}\fxy=\int_{B}\int_{A}|f(\fxx,\fxy)|\,{\rm d}\fxy\,{\rm d}\fxx,
\]
where we have written $\fxz=(\fxx,\fxy)$. It further states, that if any one of the integrals is finite, then
\[
\int_{A\times B}f(\fxz)\,{\rm d}{\bm z}=\int_{B}\int_{A}f(\fxx,\fxy)\,{\rm d}\fxx\,{\rm
d}\fxy=\int_{A}\int_{B}f(\fxx,\fxy)\,{\rm d}\fxy\,{\rm d}\fxx.
\]

\subsection*{Lebesgue's dominated convergence theorem}

\hspace*{0pt}{\indent}If a sequence of functions $\{f_n\}$ is such that $f_n(\fxx)\to f(\fxx)$ for almost every
$\fxx\in\RR^N$ as $n\to+\infty$, and if there is an integrable function $g$ such that $|f_n(\fxx)|\leq g(\fxx)$ almost
everywhere, then
\[
\int_{\RR^N}f_n(\fxx)\,\rmd\fxx\to\int_{\RR^N}f(\fxx)\,\rmd\fxx.
\]
We often use the following direct consequence: if $A_n$ is a decreasing sequence of measurable sets with bounded
measure then $\rm{measure} (A_n)\mapsto \rm{measure} (A).$ To prove this, apply Lebesgue's theorem to the
characteristic functions of $A_n$ and $A$,  $\bmone_{A_n}$ and $\bmone_A$.

We also use the following result, which is a direct consequence of the dominated convergence theorem.

\subsection*{Interchanging differentiation and integration}

\hspace*{0pt}{\indent}Suppose that a function $f$ defined on $(t_0,t_1)\times\RR^N$, where $(t_0,t_1)$ is any interval
of $\RR$, is such that $t\mapsto f(t,\fxx)$ is continuously differentiable (for almost every $\fxx\in\RR^N$) on some
interval $[a,b]\subset (t_0,t_1)$. If there exists an integrable function $g$ such that for all $t\in[a,b]$
\[
\bigg|\frac{\partial f}{\partial t}(t,\fxx)\bigg|\leq g(\fxx) \quad\text{almost everywhere},
\]
then the integral $I(t)=\int_{\RR^N}f(t,\fxx)\,\rmd\fxx$ is differentiable for $t\in(a,b)$ and
\[
\frac{dI}{dt}(t)=\int_{\RR^N}\frac{\partial f}{\partial t}(t,\fxx)\,\rmd\fxx.
\]
A brief but comprehensive discussion of the Lebesgue integral can be found in the classic textbook by Walter Rudin
\cite{Rudin:1966:RCA}.

\vspace{5pt}


\subsection{A   framework for sets and images}
 We  start by fixing a simple and handy  functional
framework for images and sets, which will be maintained throughout the book. Until now, we have been vague about the
domain  of definition of an image. On one hand, a real digital image is defined on a finite grid. On the other  hand,
standard interpolation methods  give a continuous representation defined on a finite
 domain of $\mathbb R^N$, usually a rectangle. Now, it is
convenient to have images defined on all of $\mathbb R^N$, but it is not convenient to extend them by making them zero
outside their original domains of definition because that would make them discontinuous.  So an usual way is to extend
them into a continuous function tending to a constant at infinity. One way to do that is illustrated in Figure
\ref{figureextensionperiodique}. First, an extension to a wider domain is performed by reflection across the domain's
boundary and periodization.  Then, it  is easy to let the function fade at infinity or to make it compactly supported.
This also means that we fix a value  at infinity for $u$, which we denote by $u(\infty)$.  We denote the  topological
completion of  $\RR^N$ by this infinity  point by $\SN=\RR^N\cup\{\infty\}$, which can also be denoted
$\overline{\RR^N}$. Let us justify the notation.

\begin{proposition}\label{defSN} Consider the sphere $S_N=\{\fxz\in
\RR^{N+1},\; ||\fxz||=1\}.$  Then the mapping $T:\; \RR^N\cup\{\infty\}\to \SN$ defined by
$$T(\fxx)=
\left(\frac{2\fxx}{1+\fxx^2},\;\frac{\fxx^2-1}{\fxx^2+1}\right)
$$
is a homeomorphism (that is, a continuous bijection with continuous inverse.)
\end{proposition}
 This is easily checked (Exercise \ref{exodefSN}).

\begin{definition} We denote by $\mathcal F$ the set of continuous
functions on $\SN$, which can be identified with the set of continuous functions on $\RR^N$  tending to some constant
at infinity. The natural norm of $\mathcal F$ is
\begin{equation}
  \|u\|_{\mathcal F}=\sup_{\fxx\in \RR^N}|u(\fxx)|.
  \end{equation}
  We say that an  image $u$ in $\mathcal F$ is $C^1$,
  if the function $u$ is $C^1$ at each point $\fxx\in \RR^N$. We
  define in the same way the $C^2$,... $C^\infty$ functions of $\mathcal  F$.
\end{definition}


\begin{figure}[!t]
\setkeys{Gin}{width=10cm} \centerline{
\includegraphics{fig01.03.1.eps}
} \caption[Image extension]{\label{extension} Image extension by symmetry, followed by periodization. Then the image
can be extended continuously to the rest of the plane into a function which is constant for $\fxx$ large. The purpose
of these successive extensions of $u$ to all of $\mathbb R^N$ is to facilitate the definition of certain operations on
$u$, such as convolution with smoothing kernels, and, at the same time, to preserve the continuity of $u$. This method
of extending a function is widely used in image processing; in particular, it is used in most compression and
transmission standards. For instance, the discrete cosine transform (DCT) applied to the initial data $u$, restricted
to $[0,1]^N$, is easily interpreted as an application of the FFT to the symmetric extension of $u$.
}\label{figureextensionperiodique}
\end{figure}

\begin{definition}\label{defuniformcontinuity}
We say that   a function $u$ defined on $\RR^N$ is uniformly continuous if for every $\fxx, \; \fxy$,
\[
|u(\fxx+\fxy)-u(\fxx)|\leq\varepsilon(|\fxy|),
\]
for some function $\varepsilon$ called modulus of continuity of $u$, satisfying $\lim_{s\to  0}\varepsilon(s)=0$.
\end{definition} Continuous functions on a compact set are uniformly continuous, so
  functions of $\mathcal F$ are
 uniformly continuous.
 We shall often consider the level sets of functions in
 $\mathcal F$, which simply are compact sets of $\SN$.
 \begin{definition} We denote by  $\mathcal L$ the set of all
 compact sets of $\SN$.
 \end{definition}
 These sets are easy to characterize:
 \begin{proposition}\label{classificationdeL}
 The elements   of $\mathcal L$  are of three kinds:
 \begin{itemize}
 \item compact subsets of $\RR^N$
 \item $F\cup\{\infty\}$, where $F$ is a compact set of $\RR^N$.
 \item $F\cup\{\infty\}$, where $F$ is  an
  unbounded closed subset of  $\RR^N$
  \end{itemize}
 \end{proposition}
 \begin{proof}
 Indeed, $B\cap \RR^N$ is a closed set of $\RR^N$ and is therefore
 either  a bounded compact set or an unbounded closed set of
 $\RR^N$.  In the latter case, $B$ must contain $\infty$.
 \end{proof}


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