%gmChap17.tex

\graphicspath{{./figures/}}

\chapter[Scale Spaces and PDE's]{Scale Spaces and Partial Differential Equations\label{Chap17}}

This chapter and the next one are devoted to an axiomatic
development of image smoothing. Our approach is based on the
notion of a {\em scale space}:

\begin{definition}\label{definition17.1}A {\em scale space} is a family of image
(function) operators $\{T_t\}$, $t\in\RR^+$, defined on $\mathcal
 F$. \end{definition}

Although this concept is completely abstract, it is clearly based
on work presented in previous chapters. One can think of an
operator $T_t$ belonging to a scale space as the asymptotic limit
of iterated filters, and in fact, the main purpose for developing
this abstract theory is to classify and model the possible
asymptotic behaviors of iterated filters. The program proceeds as
follows: We first introduce several properties that smoothing
operators are reasonably expected to have. These properties will
be recognized as abstractions of results about iterated filters
that we have already encountered; in particular, the function $F$
that has played such an important role in relating iterated
operators to differential equations appears in Definition
\ref{definition17.5}.  At this stage, we will have formally
identified scale spaces with the operator mapping $u_0$ to $u(t)$,
where $u(t,\fxx)$ is a solution of a parabolic partial
differential equation
$$\frac{\partial u}{\partial  t}=F(D^2u,  Du, u, \fxx, t).$$
 The next step is to define the now-familiar
invariants for scale spaces, one at a time, and then deduce
properties that $F$ must have based on the assumed invariants of
$\{T_t\}$. This will lead, for example, to a complete
characterization of the function $F$ for a linear scale space as
the Laplacian.

The chapter contains seven figures that illustrate some of the
concepts. Figures \ref{heateqnnotcontrastinvariant},
\ref{amssiscontrastinvariant}, \ref{tjunctions}, and \ref{Julesz}
are placed at the end of the chapter. Figure
\ref{heateqnnotcontrastinvariant} illustrates numerically that
linear smoothing is not contrast invariant. On the other hand,
Figure \ref{amssiscontrastinvariant} shows experimentally that the
scale space AMSS is contrast invariant. The significance of
contrast invariance for smoothing T-junctions is illustrated in
Figure \ref{tjunctions}. Figure \ref{Julesz} illustrates one of
the most important twentieth century discoveries about human
vision and compares it with computer vision.

\section{Basic assumptions about scale spaces}

  In our context, the operators $T_t$ are smoothing
operators and the functions $u$ are images. Thus, given an image
$u_0$, $T_tu_0=u(t,\cdot)$ is the image $u_0$ smoothed at scale
$t$. It is natural to abstract the idea that an image smoothed at
scale $t$ can be obtained from the image smoothed at scale $s$,
$s<t$, without having to ``go back'' to the original image $u_0$.
This concept is illustrated in Figure \ref{pyramid} and formulated
in the next definition.

\begin{definition}\label{definition17.2}A scale space $\{T_t\}$ is said to be {\em
pyramidal} if there is another family of operators
$\{T_{t+h,t}\}:\mathcal F\to  \mathcal F$, $h\geq0$, called
transition operators, such that
\[ T_{t+h}=T_{t+h,t}T_t\quad\text{and}\quad T_0=I, \] where $I$
denotes the identity operator. \end{definition}

We will sometimes denote the transition operators by
$\{T_{s,t}\}$, $0\leq t\leq s$. Then $T_s=T_{s,t}T_t$, $h=s-t$,
and $T_{t,t}=I$. Most, but not all, results are about pyramidal
scale spaces. An important exception is Lemma \ref{lemma17.20},
which is a key result in our program.

A strong version of ``pyramidal''  is the semigroup property.
Recall that we have already encountered this idea in Chapter
\ref{Chap8} in connection with a dilation or an erosion generated
by a convex set.

\begin{definition}\label{definition17.3}A scale space $\{T_t\}$ is said to be {\em
recursive} if $T_0=I$ and \[ T_sT_t=T_{s+t}\quad\text{for
all}\quad s,t\in\RR. \] \end{definition}

Note that if $\{T_t\}$  is recursive, then $T_t$ can be obtained
by iterating $T_{t/n}$ $n$ times. Another intuitive concept is
that of ``locality.'' The thought that the action of a smoothing
operator on a function $u$ at $\fxx$ would be sensitive to what
the function did far from $\fxx$ just does not make sense. This
means that we want the action of the transition operators to
depend essentially on the values of $u(\fxy)$ for $\fxy$ near
$\fxx$. Furthermore, we have had ample opportunity in earlier
chapters to see the technical importance of locality. The related
property of being monotonic is also intuitively and technically
important. We combine these notions is the next definition.

\begin{definition}\label{definition17.4}
A scale space $\{T_t\}$ satisfies a {\em local comparison principle}
 if the following implications are true: For all $u$ and $v$ in the domain of
 definition, $u(\fxy)\leq v(\fxy)$ for $\fxy$ in some neighborhood of $\fxx$
    implies that
\[
T_{t+h,t}u(\fxx)\leq T_{t+h,t}v(\fxx)+o(h)\quad\text{for all sufficiently small $h$.}
\]
If $u(\fxy)\leq v(\fxy)$ for all $\fxy\in\RR^N$, then
\[
T_{t+h,t}u(\fxx)\leq T_{t+h,t}v(\fxx)\quad\text{for all $\fxx\in\RR^N$ and all $h>0$.}
\]
\end{definition}

Our goal is to establish a classification of  scale spaces. To do
this, we need an assumption stating that a smooth image evolves
smoothly with the scale space. From what we have seen in previous
chapters, it should not be surprising that it is sufficient to
assume this kind of property for quadratic functions. Now,
quadratic functions are not allowed to us, as they do not belong
to $\mathcal F$. Now, there are functions in $\mathcal F$ which
coincide locally with  every quadratic functions and this  is
enough for our scopes.
\begin{definition}\label{definition17.5bis} We say that  $u$ is a ``quadratic function
around $\fxx$" if it belongs to $\mathcal F$ and if for all $\fxy$
in some  $B(\fxx,  r),$ $r>0$, one has
$$u(\fxy)=\frac1{2}\langle A(\fxy-\fxx),\fxy-\fxx\rangle +\langle
p,\fxy-\fxx\rangle+c, $$     where $A=D^2u(\fxx)$ is an $N\times
N$ matrix, $p=Du(\fxx)$ is a vector in $\RR^N$, and $c=u(\fxx)$ is
a constant.

\end{definition}


From the semigroup point of view, the next assumption implies the
existence of an infinitesimal generator for the semigroup $T_t$.

\begin{figure}[!ht]
\setkeys{Gin}{width=8cm}
\centerline{
\includegraphics{fig17.02.1.eps}
} \caption[The visual pyramid of scale space]{The visual pyramid
of scale space.  Perception is thought of as a flow of images
passing through transition operators $T_{t,s}$. These operators
receive an image previously analyzed at scale $s$ and deliver an
image analyzed at a larger scale $t$. The scale $t=0$ corresponds
to the original percept. In this simple model, the perception
process is irreversible: There is no feedback from coarse scales
to fine scales.\label{pyramid}}
\end{figure}


\begin{definition} \label{definition17.5}  A
scale space $\{T_t\}$ is said to be {\em regular} if there exists
a function \[ F:(A,p,\fxx,c,t)\mapsto F(A,p,\fxx,c,t) \] that is
continuous with respect to $A$ and such that for every quadratic
function $u$ around $\fxx$,
\begin{equation}\label{eq204}
\frac{T_{t+h,t}u(\fxx)-u(\fxx)}{h}\to
F(D^2u(\fxx),Du(\fxx),\fxx,u(\fxx),t)\quad\text{as}\quad h\to0.
\end{equation}
\end{definition}
It is useful to write \eqref{eq204} as
$T_{t+h,t}u(\fxx)-u(\fxx)=hF(A,p,\fxx,c,t)+o(h)$. Then, replacing
$t$ with $t-h$ shows that
\begin{equation}\label{eq204a}
T_{t,t-h}u(\fxx)-u(\fxx)=hF(A,p,\fxx,c,t-h)+o(h).
\end{equation}
Then, if $F$ is continuous in $t$,
\begin{equation}\label{eq204b}
\frac{T_{t,t-h}u(\fxx)-u(\fxx)}{h}\to F(A,p,\fxx,c,t)\quad\text{as}\quad h\to0.
\end{equation}

We encountered the notion of causality in section
\ref{section2.6}. The idea was  quite simple, if not precise: As
scale increases, no new features should be introduced by the
smoothing operators. The image at scale $t'>t$ should be simpler
than the image at scale $t$. Since we will constantly be
considering scale spaces that are pyramidal and regular, and that
satisfy the local comparison principal, it will be convenient to
give these scale spaces a name. The causality entails a further
property for $F$:
\begin{definition}\label{definition17.6}A scale space $\{T_t\}$ is said to be {\em causal} if
it is pyramidal and regular, and if it satisfies the local
comparison principle.
\end{definition}


\begin{lemma}\label{lemma17.7}If the scale space $\{T_t\}$ is causal,  then the function $F$ is nondecreasing with respect to its first argument, that is, if $A\leq B$, where $A$ and $B$ are symmetric matrices, then
\begin{equation}\label{eq206}
F(A,p,c,\fxx,t)\leq F(B,p,c,\fxx,t).
\end{equation}
\end{lemma}
\begin{proof} Let $A$ and $B$ be any $N\times N$ symmetric
matrices with $A\leq B$, and let $p$ be any $N$-dimensional
vector. Consider the  quadratic functions $Q_A$ and $Q_B$ around
$\fxx$ defined by
\begin{align*}
Q_A(\fxy)=&\; c+\langle p,\fxy-\fxx\rangle+\frac1{2}\langle A(\fxy-\fxx),\fxy-\fxx\rangle;\\
Q_B(\fxy)=&\; c+\langle p,\fxy-\fxx\rangle+\frac1{2}\langle B(\fxy-\fxx),\fxy-\fxx\rangle.
\end{align*}
Then for fixed $\fxx$ and all $\fxy$ in a neighborhood of $\fxx$,
$Q_A(\fxy)\leq Q_B(\fxy)$. Using the local comparison principle,
we conclude that $T_{t+h,t}Q_A(\fxx)\leq T_{t+h,t}Q_B(\fxx)$.
Noting that $Q_A(\fxx)=Q_B(\fxx)=c$ and using the regularity of
$\{T_t\}_{t\in\RR^+}$, we see that
\[
\lim_{h\to0}\frac{T_{t+h,t}Q_A(\fxx)-Q_A(\fxx)}{h}\leq \lim_{h\to0}\frac{T_{t+h,t}Q_B(\fxx)-Q_B(\fxx)}{h},
\]
which is the inequality $F(A,p,c,\fxx,t)\leq F(B,p,c,\fxx,t)$.
\end{proof}

We will see in the next section that the causality assumption
implies that the scale space is governed by a PDE.

\section{Causal scale spaces are governed by PDEs}

The next result, Theorem \ref{theorem17.8}, should be no surprise.
It just says that for causal scale spaces, the regularity
condition, which is defined in terms of quadratic forms, transfers
directly to functions $u$ that are $C^2$. This is a fundamental,
although easily established, step in our program. Once we have
established Theorem 17.8, we are ready to introduce invariants:
Postulate that the scale space has certain invariance properties
and conclude that $F$ must have certain properties. This will tell
us that causal scale spaces with certain invariances will be
governed by a general class of PDEs.

\begin{theorem}\label{theorem17.8}Assume that the scale space $\{T_t\}$ is causal and that $u$ is $C^2$ at $\fxx$. Then there exists a function $F$ such that for all $\fxx\in\RR^N$,
\begin{equation}\label{eq205}
\frac{T_{t+h,t}u(\fxx)-u(\fxx)}{h}\to F(D^2u(\fxx),Du(\fxx),u(\fxx),\fxx,t)\quad\text{as}\quad h\to0.
\end{equation}
\end{theorem}

\begin{proof}
Since we have assumed that $u$ is $C^2$ at $\fxx$, we can expand $u$ near $\fxx$ as
\[
u(\fxy)=u(\fxx)+\langle Du(\fxx),\fxy-\fxx\rangle+\frac1{2}\langle D^2u(\fxx)(\fxy-\fxx),\fxy-\fxx\rangle+o(|\fxx-\fxy|^2).
\]
For $\varepsilon>0$, define the quadratic functions $Q^+$ and
$Q^-$ around $\fxx$ by
\begin{align*}
Q^+(\fxy)=&\;u(\fxx)+\langle Du(\fxx),\fxy-\fxx\rangle+\frac1{2}\langle D^2u(\fxx)(\fxy-\fxx),\fxy-\fxx\rangle+\frac1{2}\varepsilon\langle \fxy-\fxx),\fxy-\fxx\rangle;\\
Q^-(\fxy)=&\;u(\fxx)+\langle Du(\fxx),\fxy-\fxx\rangle+\frac1{2}\langle D^2u(\fxx)(\fxy-\fxx),\fxy-\fxx\rangle-\frac1{2}\varepsilon\langle \fxy-\fxx),\fxy-\fxx\rangle.
\end{align*}
For sufficiently small $|\fxy-\fxx|$,
\[
Q^-(\fxy)\leq u(\fxy)\leq Q^+(\fxy).
\]
Use the facts that the scale space $\{T_t\}$ is pyramidal  (so the
transition operators exist) and that it satisfies the local
comparison principle to deduce that
\[
T_{t+h,t}Q^-(\fxx)-o(h)\leq T_{t+h,t}u(\fxx)\leq
T_{t+h,t}Q^+(\fxx)+o(h).
\]
 Since $Q^-(\fxx)=u(\fxx)= Q^+(\fxx)$, we have
\[
T_{t+h,t}Q^-(\fxx)-Q^-(\fxx)-o(h)\leq T_{t+h,t}u(\fxx)-u(\fxx)\leq
T_{t+h,t}Q^+(\fxx)-Q^+(\fxx)+o(h).
\]
Now divide by $h$ and let it tend to zero. Since $\{T_t\}$ is
regular we have the following limits:
\begin{align*}
\lim_{h\to0}\frac{T_{t+h,t}Q^-(\fxx)-Q^-(\fxx)}{h}\leq&\,\liminf_{h\to0}\frac{T_{t+h,t}u(\fxx)-u(\fxx)}{h}\leq\limsup_{h\to0}\frac{T_{t+h,t}u(\fxx)-u(\fxx)}{h}\\
\leq&\,\lim_{h\to0}\frac{T_{t+h,t}Q^+(\fxx)-Q^+(\fxx)}{h}.
\end{align*}
Thus,
\begin{align*}
F(D^2u(\fxx)-\varepsilon I,Du(\fxx),u(\fxx),\fxx,t)\leq&\liminf_{h\to0}\frac{T_{t+h,t}u(\fxx)-u(\fxx)}{h}\\
\leq&\limsup_{h\to0}\frac{T_{t+h,t}u(\fxx)-u(\fxx)}{h}\\
\leq&F(D^2u(\fxx)+\varepsilon I,Du(\fxx),u(\fxx),\fxx,t).
\end{align*}
Part of the regularity assumption is that $F$ is continuous in its first argument, so letting $\varepsilon$ tend to zero shows that
\[
\lim_{h\to0}\frac{T_{t+h,t}u(\fxx)-u(\fxx)}{h}= F(D^2u(\fxx),Du(\fxx),u(\fxx),\fxx,t). \qedhere
\]
\end{proof}

This is about all we can conclude concerning  the function $F$; to
deduce more about $F$, we must assume more about the scale space.
Most, but not all, of these assumptions will be that the scale
space is invariant under some group of operations. Some of these
invariants, like affine invariance, are rather special. The first
one we consider is, however, an invariance we naturally expect all
smoothing operators to have: Smoothing should not alter constants
and smoothing should commute with the addition of constants.

\begin{definition}\label{definition17.9}A pyramidal scale space $\{T_t\}$ is said to be
{\em invariant under grey level translations} $($or {\em commutes
with the addition of constants}$)$  if
\begin{equation}\label{eq207}
T_{t+h,t}[0](\fxx)=0\quad\text{and}\quad T_{t+h,t}(u+C)(\fxx)=T_{t+h,t}u(\fxx)+C
\end{equation}
for all $u$, all constants $C$, and all $\fxx\in\RR^N$.
\end{definition}
If $T_{t+h,t}$ is a linear filter defined by
$T_{t+h,t}u=\varphi*u$, then this axiom is equivalent to the
condition $\int\varphi(\fxx)\,\rmd \fxx=1$.


\begin{proposition}\label{proposition17.10}Let $\{T_t\}$ be a causal scale space that is
invariant under grey level translations. Then its associated
function $F:(A,p,c,\fxx,t)\mapsto F(A,p,c,\fxx,t)$ does not depend
on $c$. Furthermore, $F(0,0,c,\fxx,t)=0$.
\end{proposition}

\begin{proof}Consider a quadratic function around $\fxx$,
$u(\fxy)=(1/2)\langle A(\fxy-\fxx),\fxy-\fxx\rangle +\langle p,\fxy-\fxx\rangle+c$, and let $C$ be an arbitrary real number. By the regularity assumption
\[
\frac{T_{t+h,t}(u+C)(\fxx)-(u+C)(\fxx)}{h}\to F(A,p,c+C,\fxx,t)\quad\text{as}\quad h\to0.
\]
Using the grey level translation invariance and regularity again,
\[
\frac{T_{t+h,t}(u+C)(\fxx)-(u+C)(\fxx)}{h}=\frac{T_{t+h,t}u(\fxx)+C-u(\fxx)-C}{h}\to F(A,p,c,\fxx,t)
\]
as $h\to0$. These last two limits imply that $F(A,p,c+C,\fxx,t)=F(A,p,c,\fxx,t)$, so $F$ does not depend on $c$. If $A=0$ and $p=0$, then $T_{t+h,t}(u)(\fxx)-(u)(\fxx)=c-c=0$ and $F(0,0,c,\fxx,t)=0$.
\end{proof}

From now on, we assume that the scale space is causal and
invariant under grey level translations. We will thus suppress $c$
and write $F(A,p,c,\fxx,t)=F(A,p,\fxx,t)$.

\section{Scale spaces yield viscosity solutions}

We are going to prove a result that connects a causal scale space
$\{T_t\}$ with a viscosity solution of the PDE associated with
$\{T_t\}$. In fact, we will prove that $T_tu_0$ is a viscosity
solution of the equation
\begin{equation}\label{eq2010}
\frac{\partial u}{\partial t}(t,\fxx)=F(D^2u(\fxx), Du(\fxx),\fxx, t),
\end{equation}
where $F$ is the function associated with $\{T_t\}$ by regularity
(Definition \ref{definition17.5}).

\begin{theorem}\label{theorem17.11}Assume that a scale space $\{T_t\}$ is causal and
commutes with grey level translations; assume also that $F$ is
continuous in $t$. Then the function $u$ defined by
$u(t,\fxx)=T_tu_0(\fxx)$ is a viscosity solution of
\eqref{eq2010}.
\end{theorem}

\begin{proof}We will show that $u$ is a viscosity subsolution; the
proof that it is also a viscosity supersolution is a similar
argument with the inequalities going in the opposite direction.

Assume that $\varphi$ is $C^\infty$ and that
$(t,\fxx)\in(0,+\infty)\times\RR^N$ is a point at which the
function $u-\varphi$ has a strict local maximum. The point
$(t,\fxx)$ is fixed, so we will denote the variable by $(s,\fxy)$.
We need to show that
\begin{equation}\label{eq2015}
\frac{\partial\varphi}{\partial t}(t,\fxx)-F(D^2\varphi(t,\fxx),D\varphi(t,\fxx),\fxx,t)\leq0.
\end{equation}
(Note that we would usually consider two cases: (1)
$D\varphi(t,\fxx)\not=0;$ (2) $D\varphi(t,\fxx)=0$ and
$D^2\varphi(t,\fxx)=0$. Since $F(0,0,\fxx,t)=0$ by Proposition
\ref{proposition17.10}, it is sufficient to prove \eqref{eq2015}.)

On the basis of Lemma \ref{lemma15.5}, we assume that $\varphi$ is
of the form $\varphi(s,\fxy)=f(\fxy)+g(s)$. Since the operators
commute with the addition of constants, we may also assume that
$u(t,\fxx)=\varphi(t,\fxx)=f(\fxx)+g(t)$. Of course, both $f$ and
$g$ are $C^\infty$. Thus, for $(s,\fxy)$ in some neighborhood of
$(t,\fxx)$, we have $u(s,\fxy)\leq\varphi(s,\fxy)=f(\fxy)+g(s)$.
In particular, we have
\[
u(t-h,\fxy)\leq f(\fxy)+g(t-h)
\]
for all sufficiently small $h>0$. Since the operators $T_{t,t-h}$ satisfy the local comparison principle and commute with the addition of constants, we have
\[
T_{t,t-h}u(t-h,\cdot)(\fxx)\leq T_{t,t-h}f(\fxx)+g(t-h).
\]
By definition of the transition operators, $T_{t,t-h}u(t-h,\cdot)(\fxx)=u(t,\fxx)=f(\fxx)+g(t)$. Thus, we see that
\[
g(t)-g(t-h)\leq T_{t,t-h}f(\fxx)-f(\fxx),
\]
which by \eqref{eq204a} we can write as
\[
g(t)-g(t-h)\leq hF(D^2f(\fxx),Df(\fxx),\fxx,t-h)+o(h).
\]
Divide by $h$, use the fact the $F$ is continuous in $t$, let $h$ tend to zero, and conclude that
\[
g'(t)\leq F(D^2f(\fxx),Df(\fxx),\fxx,t).
\]
Since $\partial\varphi/\partial t=g'$, $D^2\varphi=D^2f$, and $D\varphi=Df$, this proves the result.
\end{proof}

\section{Scale space invariants and implications for $F$}

We have already seen the implication for $F$ of assuming that a
scale space $\{T_t\}$ is invariant under the addition of constants
(Proposition \ref{proposition17.10}). This section is devoted to
continuing this program: Assume an invariant for $\{T_t\}$ and
deduce its implication for $F$.

\subsection{Translation, rotation, and reflection}

These invariants concern the underlying space $\RR^N$, and they
are easily defined. Translation invariance for operators was
defined in Definition \ref{definition6.4} using the translation
operator $\tau_{\fxz}$: $\tau_{\fxz}u(\fxx)=u(\fxx-\fxz)$ for all
$\fxx,\fxz\in\RR^N$.

\begin{definition}\label{definition17.12}A pyramidal scale space $\{T_t\}$ is said to be {\em translation invariant} if
\begin{equation}\label{eq2017}
T_{t+h,t}\tau_{\fxz}=\tau_{\fxz}T_{t+h,t}\quad\text{for all $\fxz\in\RR^N$, $t\geq0$, and $h\geq0$}.
\end{equation}
\end{definition}

\begin{proposition}\label{proposition17.13}
Assume that $\{T_t\}$ is a causal, translation invariant scale space. Then its associated function $F$ does not depend on $\fxx$.
\end{proposition}

\begin{proof}Consider   two quadratic functions around 0 and $\fxx$ respectively
  defined by
\[
u(\fxy)=\frac1{2}\langle A\fxy,\fxy\rangle + \langle p,\fxy\rangle
+c\quad\text{and}\quad \tau_{\fxx}u(\fxy)=\frac1{2}\langle
A(\fxy-\fxx),\fxy-\fxx\rangle + \langle p,\fxy-\fxx\rangle +c
\]
By the regularity assumption,
\begin{align}\label{eq2018a}
T_{t+h,t}u(0)-u(0)&=hF(A,p,0,c,t)+o(h);\\
 T_{t+h,t}\tau_{\fxx}u(\fxx)-\tau_{\fxx}u(\fxx)&=hF(A,p,\fxx,c,t)+o(h).\label{eq2019}
\end{align}
By translation invariance,
\[
T_{t+h,t}\tau_{\fxx}u(\fxx)-\tau_{\fxx}u(\fxx)=\tau_{\fxx}T_{t+h,t}u(\fxx)-\tau_{\fxx}u(\fxx)=T_{t+h,t}u(0)-u(0).
\]
Thus we see from \eqref{eq2018a} and \eqref{eq2019} that $hF(A,p,0,c,t)=hF(A,p,\fxx,c,t)+o(h)$. Divide both sides by $h$ and let $h\to0$ to see that
\[
F(A,p,\fxx,c,t)=F(A,p,0,c,t). \qedhere
\]
\end{proof}

This takes care of translations; rotations and reflections are combined in the group of linear isometries. If $P$ is a linear isometry of $\RR^N$, then the function $Pu$ is defined by $Pu(\fxx)=u(P\fxx)$.

\begin{definition}\label{definition17.14}A pyramidal scale space $\{T_t\}$ is said to be {\em Euclidean invariant (or isotropic)} if
\begin{equation}\label{eq2021}
PT_{t+h,t}=T_{t+h,t}P
\end{equation}
for all linear isometries $P$ of\,  $\RR^N$, all $t\geq0$, and all $h\geq0$.
\end{definition}

We denote the group  of linear isometries of $\RR^N$ by
$O_N=O(\RR^N)$. Any  transform $P\in O_N$ can be represented
uniquely by an $N\times N$ orthogonal matrix $P$, assuming an
orthonormal basis. We do not make a distinction between the
operator $P$ and the matrix $P$. If $P\in O_N$, then recall that
its transpose $P'\in O_N$, and $PP'=I$. Recall also that given a
symmetric matrix $A$ there is always a $P\in O_N$ such that $PAP'$
is diagonal. Euclidean invariance is illustrated in Figure
\ref{nonisotropic}.

\begin{lemma}\label{17.15}If a translation invariant causal scale space $\{T_t\}$ is isotropic, then for every $R\in O_N$,
\begin{equation}\label{eq2022}
F(RAR', Rp, t)=F(A,p,t),
\end{equation}
where $F$ is the function associated with $\{T_t\}$ by regularity.
\end{lemma}

\begin{proof}Consider a quadratic function around 0, $u(\fxy)=(1/2)\langle A\fxy,\fxy\rangle+\langle p,\fxy\rangle$ and let $F$ be the function associated with $\{T_t\}$.  We know that the value of $F$ is determined by the action of $T_{t+h,t}$ on $u$ at $t$, that is,
\[
T_{t+h,t}u(\fxx)-u(\fxx)=hF(A,p,t)+o(h).
\]
In particular,
\begin{equation}\label{eq2018}
\lim_{h\to0}\frac{T_{t+h,t}u(0)-u(0)}{h}=F(A,p,t).
\end{equation}
Let $R$ be any element of $O_N$. Then
\[
u(R\fxy)=\frac1{2}\langle AR\fxy,R\fxy\rangle+\langle p,R\fxy\rangle
=\frac1{2}\langle R'AR\fxy,\fxy\rangle+\langle R'p,\fxy\rangle.
\]
Thus we know immediately that
\[
T_{t+h,t}(u\circ R)(\fxx)-u(R\fxx)=hF(R'AR,R'p,t)+o(h),
\]
where $u\circ R$ denotes the function defined by $u\circ R(\fxy)=u(R\fxy)$.
The assumption that $\{T_t\}$ is isotropic means that $T_{t+h,t}(u\circ R)(\fxx)=
T_{t+h,t}u(R\fxx)$, so
\[
T_{t+h,t}(u\circ R)(\fxx)-u(R\fxx)=T_{t+h,t}u(R\fxx)-u(R\fxx).
\]
From this we conclude that
\[
\lim_{h\to0}\frac{T_{t+h,t}(u\circ R)(\fxx)-u(\fxx)}{h}=\lim_{h\to0}\frac{T_{t+h,t}u(R\fxx)-u(R\fxx)}{h}=F(R'AR,R'p,t).
\]
By letting $\fxx=0$ in these limits, we conclude from \eqref{eq2018} that
\[
F(A,p,t)=F(R'AR,R'p,t).
\]
Replacing $R$ with $R'$ completes the proof.
\end{proof}

\begin{figure}[!t]
\setkeys{Gin}{width=10cm}
\centerline{
\includegraphics{fig17.04.1.eps}
}
\caption[A nonisotropic filter]{An isotropic filter and a nonisotropic filter. The left frame contains simple shapes that can be deduced from each other by rotations. The center image is the closing of the left image by a horizontal rectangle of size $6\times2$ pixels. This nonisotropic filter produces different results, depending on the shapes orientations. The right image is the closing of the left image by a circle of radius 4 pixels, which has the same area, up to the pixel precision, as the rectangle used in the center image. This filter is isotropic; thus, as one can see, the resulting shapes can be deduced from each other by rotations.\label{nonisotropic}
}
\end{figure}



\subsection{Contrast invariance}

\begin{definition}\label{definition17.16}A pyramidal scale space $\{T_t\}$ is said to be
{\em contrast invariant} if
\[
g\circ T_{t+h,t}=T_{t+h,t}\circ g
\]
for any nondecreasing continuous function $g:\RR\to\RR$.
\end{definition}

An immediate consequence of this definition is that a contrast
invariant scale space commutes with the addition of constants,
that is, it satisfies Definition \ref{definition17.9}. To see
this, just take $g(s)=0$ and $g(s)=s+C$. Thus, in the next lemma,
the function $F$ does not depend on $c$.

\begin{lemma}\label{lemma17.17}If a translation invariant causal scale space
$\{T_t\}$ is contrast invariant, then its associated function $F$
satisfies the following condition:
\begin{equation}\label{eq2025}
F(\mu A+\lambda p\otimes p,\mu p,t)=\mu F(A,p,t),
\end{equation}
where $A$ is any symmetric $N\times N$ matrix, $p$ is any $N$-dimensional vector, $\lambda$ is any real number, and $\mu$ is any real number greater than or equal to zero.
\end{lemma}

\begin{proof}   Recall that $p\otimes p$ denotes the $N\times
N$ matrix whose entries are $p_ip_j$, $i,j\in \{1,2,\ldots,N\}$.
 Given  $C^2$ functions $u$ and $g$, we
have these two applications of the chain rule:
\begin{equation}\label{eq2026}
D(g(u))=g'(u)Du,\quad\text{and}\quad D^2(g(u))=g'(u)D^2u+g''(u)Du\otimes Du.
\end{equation}
  Choose any quadratic function around 0 of the
form
\[
u(\fxy)=(1/2)\langle A\fxy,\fxy\rangle+\langle p,\fxy\rangle.
\]
  We know from
the assumptions and equations \eqref{eq2026}, plus the relations
$u(0)=0$, $Du(0)=p$, and $D^2u(0)=A$, that
\[
T_{t+h,t} g(u)(0)-g(0)=hF(g'(0)A+g''(0)p\otimes p, g'(0)p,t)+o(h).
\]
Since $\{T_t\}$ is contrast invariant, $T_{t+h,t} g(u)(0)=g(T_{t+h,t}u(0))$, so
\[
g(T_{t+h,t}u(0))-g(0)=hF(g'(0)A+g''(0)p\otimes p, g'(0)p,t)+o(h).
\]
From regularity, we have
\[
T_{t+h,t}u(0)-u(0)=hF(A,p,t)+o(h),
\]
so we can write $g(T_{t+h,t}u(0))=g(hF(A,p,t)+o(h))$. Thus for small enough $h$,
\[
g(T_{t+h,t}u(0))=g(0)+g'(0)(hF(A,p,t)+o(h))+o(h)
\]
and
\[
g'(0)hF(A,p,t)+g'(0)o(h))+o(h)=hF(g'(0)A+g''(0)p\otimes p, g'(0)p,t)+o(h).
\]
Dividing this by $h$ and letting $h\to0$ shows that
\[
g'(0)F(A,p,t)=F(g'(0)A+g''(0)p\otimes p, g'(0)p,t),
\]
or, since we can choose a $C^2$ contrast change $g$ with arbitrary
values for $g'(0)\geq0$ and $g''(0)\in\RR$,
\[
\mu F(A,p,t)=F(\mu A+\lambda p\otimes p, \mu p,t).
\]
\end{proof}

\subsection{Scale and affine invariance}
The main purpose of this section is  to establish a normalized
link between scale $(t)$ and space $(\fxx)$.  If $T_t$ is a causal
scale space and $h:\RR^+\to \RR^+$ is a $C^2$ increasing function,
it is easily seen that $S_t=T_{h(t)}$ also is a causal scale space
(see Exercise \ref{exerciserescalingscalespace}.) So there is no
special link on the scale, unless we give a further specification.
This specification will be given by a {\it scale invariance}
axiom.

Scale invariance means intuitively that the result of applying a
  scale space $\{T_t\}$ must  be independent of the size
of the analyzed features. This is very important for analyzing
natural images, since the same object can be captured at very
different distances and therefore at very different scales (see
Figure \ref{mutiscaleworld}).

Scale invariance is the object of  Definitions
\ref{definition17.18} and \ref{definition17.9}. The main result is
 Lemma \ref{lemma17.20} which gives a standard normalization:
Scale can be taken proportional to space.

This result can be somewhat secluded from the rest of the
invariance analysis, as we will prove it for arbitrary families of
function operators $\{T_t\}$, $t\geq0$,  not even  pyramidal.  We
shall just assume that the mapping $t:[0,\infty)\mapsto T_t$ is
one-to-one.


 The changes of scale on an image can be made by a zoom, in which case the
 zooming factor $\lambda$ gives a scale parameter. In the case of an affine transform
$A$, the square root of the determinant of $A$ also will play the
role of a scale parameter. By zoom we mean a map
$\fxx\mapsto\lambda\fxx$, $\lambda>0$, generating an image
transform $H_\lambda u(\fxx)=u(\lambda\fxx)$.



\begin{definition}\label{17.18}A family of operators $\{T_t\}$ is said to be
{\em scale invariant} if there exists a rescaling function
$t':(t,\lambda)\mapsto t'(t,\lambda)$, defined for all $\lambda>0$
and $t\geq0$, such that
\begin{equation}\label{eq2027}
H_\lambda T_{t'}=T_tH_\lambda.
\end{equation}
It $\{T_t\}$ is pyramidal, then
\begin{equation}\label{eq2027a}
H_\lambda T_{t',s'}=T_{t,s}H_\lambda,
\end{equation}
where $t'=t'(t,\lambda)$ and $s'=t'(s,\lambda)$. In addition, the
function $t'$ is assumed to be differentiable with respect to $t$
and $\lambda$, and the function  $\phi$ defined by
$\phi(t)=(\partial t'/\partial\lambda)(t,1)$ is assumed to be
continuous and positive for $t>0$.
\end{definition}

This definition implies, in particular,  that $t'$ is continuous
in $t$ and $\lambda$. Condition \eqref{eq2027a} implies
\eqref{eq2027}. It will have the advantage of making our
classification of scale-invariant scale spaces easier.
 Of course, we could not
impose the condition $t'=t$, since the scale of smoothing and the
scale of the image are covariant, as can be appreciated by
considering  the heat equation.

The assumption that  $(\partial t'/\partial\lambda)(t,1)>0$ can be
interpreted by considering the relation $H_\lambda
T_{t'}=T_tH_\lambda$ when the scale $\lambda$ increases before the
analysis by $T_t$, that is, when the size of the image is reduced
before analysis. Then the corresponding scale before reduction is
increased. Informally, we can say that the scale $t$ of analysis
increases with the size of the picture.   It is easy to determine
the function $t'$ for several classical scale spaces (Exercise
\ref{exerciseclassicalscalespaces}) and to check that it satisfies
the previous requirements.

 The next definition (axiom) introduces   the
scale space invariance under any orthographic projection of a
planar shape.   We write as usual $Au(\fxx)=u(A\fxx)$.

\begin{figure}[!t]
\setkeys{Gin}{width=10cm}
\centerline{
\includegraphics{fig17.01.1.eps}
} \caption[A multiscale word]{A multiscale world. This series of
images is an experiment to show the relative perception of objects
seen at different distances. Each photograph, after the first one,
was taken by stepping forward to produce a snapshot from a
distance closer than the one before. The rectangle in each image
outlines the part of the object that appears in the next image.
Clearly, as one gets closer to the subject, the visual aspect
changes and new structures appear. Thus, computing primitives in
an image is always a scale-dependent task, and it  depends on the
distance to objects. When we look at an object from a certain
distance, we do not perceive the very fine structure: For
instance, leaves cannot be seen in the two first photographs
because we are too far from the trees. Nor do we see them in the
last two, since we are now too close. Multiscale smoothing of a
digital image tries to emulate and actually improve this and
 phenomenon, due to an optical blur, by defining a smoothing at different
scales.  The  role of this  multiscale smoothing is to  eliminate
the finer structures at a scale $t$, but minimally modify the
image at scales above $t$. \label{mutiscaleworld}}
\end{figure}


\begin{definition}\label{definition17.19}A family of operators $\{T_t\}$ is said to be
{\em affine invariant} if it is scale invariant and if the
following conditions hold: The associated function $t'$ can be
extended to a function $t':(t,A)\mapsto  t'(t,A)$, where $t\geq0$
and $A$ is any linear mapping $A:\RR^N\to\RR^N$ with ${\rm
det}(A)\not=0$, such that $t'(t,\lambda)=t'(t,\lambda I)$ and such
that
\begin{equation}\label{eq2028}
AT_t'=T_tA.
\end{equation}
If $\{T_t\}$ is pyramidal, the transition operators $T_{t,s}$
satisfy the commutation relation
\begin{equation}\label{eq2029}
AT_{t',s'}=T_{t,s}A
\end{equation}
for all $0\leq s\leq t$, where $t'=t'(t,A)$ and $s'=t'(s,A)$.
\end{definition}

This property means that the result of applying the scale space
$\{T_t\}$ to a image is covariant with the distance and
orientation in space of the analyzed planar image (see the
introduction of Chapter \ref{Chap12}.) The fact that the function
$t'$ can be different for each scale space may seem mysterious. We
will ``fix'' this in the next lemma by showing that we can, ``up
to a rescaling" assume that scale-invariant scale spaces have all
the same scale-space function, namely $t'=\lambda t$.

\begin{lemma}\label{lemma17.20}[Scale normalization]Assume that the mapping
$t\mapsto T_t$, $t\in[0,\infty)$, is one-to-one and that $T_0=I$.
\begin{enumerate}[$(i)$]\setlength\itemsep{2pt}
\item If the family of operators $\{T_t\}$ is scale invariant,
then there exists an increasing differentiable function
$\sigma:[0,\infty)\to[0,\infty)$ such that
$t'(t,\lambda)=\sigma^{-1}(\sigma(t)\lambda).$ If the operators
$S_t$ are defined by $S_t=T_{\sigma^{-1}(t)}$, then
\begin{equation}\label{eq2030}
t'(t,\lambda)=t\lambda
\end{equation}
for the rescaled analysis $\{S_t\}$. \item If the family $\{T_t\}$
is affine invariant, then the function $t';(t,B)\mapsto t'(t,B)$
depends only on $t$ and $|{\rm det}B|$, in particular,
$t'(t,B)=t'(t,|{\rm det}B|^{1/N})$, and $t'$ is increasing with
respect to $t$. In addition, there exists an increasing
differentiable function $\sigma$ from $[0,\infty)$ to $[0,\infty)$
such that $t'(t,B)=\sigma^{-1}(\sigma(t)|{\rm det}B|^{1/N}).$ If
we set $S_t=T_{\sigma^{-1}(t)}$, then
\begin{equation}\label{eq2031}
t'(t,B)=t|{\rm det}B|^{1/N}
\end{equation}
for the rescaled analysis $\{S_t\}$.
\end{enumerate}
\end{lemma}

\begin{proof}We will prove $(ii)$ and then show how this proof can be reduced to a proof
of $(i)$.

\medskip\noindent {\bf Step 1:} We prove that
\begin{equation}\label{eq2034}
t'(t,AB)=t'(t'(t,A),B)
\end{equation}
for any linear transforms $A$ and $B$ with nonzero determinants.
To see this, write
\[
ABT_{t'(t,AB)}=T_tAB=AT_{t'(t,A)}B=ABT_{t'(t'(t,A),B)}.
\]
Since the determinant of $AB$ does not vanish, we have
$T_{t'(t,AB)}=T_{t'(t'(t,A),B)}$, and since $t\mapsto T_t$ is
one-to-one, we have \eqref{eq2034}.


\medskip\noindent {\bf Step 2: }The function $t'$ is increasing with respect to $t$.
\newline
 We begin by
proving that $t\mapsto t'(t,A)$ is one-to-one for any $A$ with
${\rm det}A\not=0$. If this were not the case, then there would be
some $A$, ${\rm det}A\not=0$, and some $s$ and $t$, $s\not=t$,
such that $t'(s,A)=t'(t,A)$. This implies that
\[
T_sA=AT_{t'(s,A)}=AT_{t'(t,A)}=T_tA.
\]
Since ${\rm det}A\not=0$, this means that $T_s=T_t$, and since
$t\mapsto T_t$ is one-to-one, we have $s=t$. Thus $t'$ is
one-to-one. By hypothesis, $T_0=I$, and since
$AT_{t'(0,A)}=T_0A=A$, we see that $t'(0,A)=0$ for all $A$. By
definition, $t'$ is continuous and nonnegative. Since $t'\mapsto
t'(t,A)$ is one-to-one and since  $t'(0,A)=0$, it is a
homeomorphism of $[0,\infty)$ onto $[0,\infty)$ for every $A$ with
nonzero determinant. Thus $t'$ is increasing in $t$.

\medskip \noindent {\bf Step 3:}  For every orthogonal matrix $R$,
\begin{equation}\label{eq2037}
t'(t,R)=t.
\end{equation}
To prove that, define $t_1=t'(t,R)$ and $t_{n+1}=t'(t_n,R)$. From
\eqref{eq2034}, $t_{n}=t'(t,R^n)$. There are two cases to reject:
 (1) $t_1<t$; (2) $t_1>t$.   In case (1), the fact that $t'$
is strictly increasing in $t$ implies that the sequence $t_n$ is
strictly decreasing. Similarly, in case (2), the sequence $t_n$ is
strictly increasing.   Since the set of orthogonal matrices is
compact, there is a subsequence $n_k$ and an orthogonal matrix $P$
such that $R^{n_k}\to P$ as $k\to\infty$. Let $m_k=n_{k+1}-n_k$.
Then $R^{m_k}\to I$ as $k\to\infty$. Since $t'$ is continuous,
$\lim_{k\to\infty}t'(t,R^{m_k})\to t'(t,I)=t$. In case (1), we
have $t=\lim_{k\to\infty}t'(t,R^{m_k})<t$, a contradiction. In
case (2) we have $t=\lim_{k\to\infty}t'(t,R^{m_k})>t$, a
contradiction again.

\medskip \noindent{\bf Step 4:} For all transforms
 $B$ that have nonzero
determinants,
\begin{equation}\label{eq2037a}
t'(t,B)=t'(t,|{\rm det}B|^{1/N}).
\end{equation}
This part of the proof is
 pure matrix theory. Let $B$
be any $N\times N$ nonsingular matrix (linear transform of
$\RR^N$). The $B$ can be written as $B=R_1DR_2$, where $R_1$ and
$R_2$ are orthogonal and $D$ is diagonal. Furthermore,
$d_{ii}=\lambda_i>0$ and the $\lambda_i$ are, up to a sign, the
eigenvalues of $B$. As a consequence, using \eqref{eq2034} and
\eqref{eq2037}, we see that
\[
t'(t,B)=t'(t,D).
\]
The matrix $D$ can be represented as $D=A(\lambda_1)R_2A(\lambda_2)R_2^{-1}\cdots R_NA(\lambda_N)R_N^{-1}$, where the mapping $A(\lambda_i)$
 is defined by $(x_1,x_2,\ldots,x_N)\mapsto(\lambda_i x_1,x_2,\ldots,x_N)$ and $R_j$ is the orthogonal mapping that interchanges $x_1$ and $x_j$. Repeated use of
\eqref{eq2034} and \eqref{eq2037} and the fact that $A(\lambda_1)A(\lambda_2)\cdots A(\lambda_N)=A(\lambda_1\lambda_2\cdots\lambda_N)$ shows that
\[
t'(t,D)=t'(t,A(\lambda_1\lambda_2\cdots\lambda_N)).
\]
Now write $(\lambda_1\lambda_2\cdots\lambda_N)^{1/N}=\lambda$ and consider the matrix $\lambda I$. As we have done above, we can write $\lambda I=A(\lambda)R_2A(\lambda)R_2^{-1}\cdots R_NA(\lambda)R_N^{-1}$. Then using \eqref{eq2034} and \eqref{eq2037} again, we see that
\[
t'(t,\lambda I)=t'(t, A(\lambda^N))=t'(t,A(\lambda_1\lambda_2\cdots\lambda_N)),
\]
and we conclude that
\[
t'(t,B)=t'(t,D)=t'(t,A(\lambda_1\lambda_2\cdots\lambda_N))= t'(t,\lambda I).
\]
By definition, $t'(t,\lambda I)=t'(t,\lambda)$, where we have used
the same notation for the function $t':(t,\lambda)\mapsto
t'(t,\lambda)$ and its extension $t':(t,\lambda I)\mapsto
t'(t,\lambda I)$. So we obtain \eqref{eq2037a}.

\medskip\noindent{\bf Step 5:} There is an increasing
differentiable function $\sigma$ that satisfies the equation
$t'(t,\lambda)=\sigma^{-1}(\sigma(t)\lambda)$, or equivalently,
$\sigma(t'(t,\lambda))=\sigma(t)\lambda$.
\newline Differentiating
the last equation with respect to $\lambda$ and then setting
$\lambda =1$, shows that
\begin{equation}\label{eq2040}
\phi\sigma'=\sigma,
\end{equation}
so it is reasonable to define $\sigma$ by
\[
\sigma(t)=\exp\Bigg(\int_1^t\frac{\rmd s}{\phi(s)}\Bigg).
\]
Since by assumption $\phi$ is continuous and $\phi(s)>0$ for $s>0$, $\sigma$ is clearly increasing and differentiable. It remains to show that $t'(t,\lambda)=\sigma^{-1}(\sigma(t)\lambda)$.

From equations \eqref{eq2034} and \eqref{eq2037}, we know that $t'(t,\mu\nu)=t'(t'(t,\mu),\nu)$ and $t'(t,1)=t$ for all positive $\mu$ and $\nu$. Differentiating both sides of the first equation with respect to $\mu$ and then setting $\mu=1$ and $\nu=\lambda$ shows that
\begin{equation}\label{eq2039}
\lambda\frac{\partial t'}{\partial\lambda}(t,\lambda)=\frac{\partial t'}{\partial t}(t,\lambda)\frac{\partial t'}{\partial\lambda}(t,1).
\end{equation}
By Definition 17.18, the function $\phi$ given by $\phi(t)=(\partial t'/\partial\lambda)(t,1)$ is continuous and positive for $t>0$. We have shown that $t'$ is strictly increasing, thus the right-hand side of \eqref{eq2039} is nonnegative. This implies that
\begin{equation}\label{eq2039a}
\frac{\partial t'}{\partial\lambda}(t,\lambda)\geq0.
\end{equation}

If $t'(t,\lambda)=\sigma^{-1}(\sigma(t)\lambda)$ is going to be true, then it is also true if we replace $\lambda$ with $\lambda/\sigma(t)$, which is the equation
$t'(t,\lambda/\sigma(t))=\sigma^{-1}(\lambda)$. This prompts us to examine the function $g$ defined by $g(t,\lambda)=t'(t,\lambda/\sigma(t))$. When we differentiate $g$ with respect to $t$, we will see that this derivative is zero:
\begin{align*}
\frac{\partial g}{\partial t}(t,\lambda)&=\frac{\partial t'}{\partial t}(t,\lambda/\sigma(t)) -\lambda \frac{\sigma'(t)}{\sigma^2(t)}\frac{\partial t'}{\partial\lambda}(t,\lambda/\sigma(t))\\
&=\frac{\partial t'}{\partial t}(t,\lambda/\sigma(t)) -\frac{\sigma'(t)}{\sigma(t)}\frac{\partial t'}{\partial t}(t,\lambda/\sigma(t))\phi(t)\quad\text{(using \eqref{eq2039})}\\
&=0\quad\text{(using $\sigma'\phi=\sigma$).}
\end{align*}
Thus, $g$ does not depend on $t$, and we know from \eqref{eq2039a} that $g$ in nondecreasing. Since $g$ is also differentiable, we conclude that $g(t,\lambda)=\beta(\lambda)$, where $\beta$ is differentiable and nondecreasing. By replacing $\lambda$ with $\lambda\sigma(t)$, we have
\begin{equation}\label{eq2041}
t'(t,\lambda)=\beta(\lambda\sigma(t)).
\end{equation}
By differentiating both sides of this equation with respect to $\lambda$ and then letting $\lambda=1$, we see that $\phi(t)=\sigma(t)\beta'(\sigma(t))=\phi(t)\sigma'(t)\beta'(\sigma(t))$. Dividing both sides by $\phi(t)$ shows that
\[
\frac{\partial\beta(\sigma(t))}{\partial t}(t)=1.
\]
Integrating this relation from zero to $t$ yields the equation $\beta(\sigma(t))=t+\beta(\sigma(0))$. Since $t'(0,\lambda)=0$, $\beta(\sigma(0))=0$ by \eqref{eq2041}, and we conclude that $\beta=\sigma^{-1}$.

\medskip\noindent{\bf Step 6:} To complete the proof of $(ii)$, we must show that the
operators $S_t$ by $S_t=T_{\sigma^{-1}(t)}$ are affine invariant
with $t'(t,\lambda)=\lambda t$. Thus let $B$ be any nonsingular
linear mapping and let $\lambda=|{\rm det}B|^{1/N}$. Then
\[
S_tB=T_{\sigma^{-1}(t)}B=BT_{t'(\sigma^{-1}(t),\lambda)}=BT_{\sigma^{-1}(\lambda\sigma(\sigma^{-1}(t)))}=BT_{\sigma^{-1}(\lambda t)}=BS_{\lambda t}.
\]

The proof of $(i)$ is just the ``image'' of the proof of $(ii)$ under the obvious mappings $B\mapsto|{\rm det}B|^{1/N}$ and $\lambda I\mapsto H_\lambda$, which entail $t'(t,B)\mapsto t'(t,|{\rm det}B|^{1/N})$, and so on.
\end{proof}

\begin{lemma}\label{17.21}If a translation invariant causal scale space $\{T_t\}$ is affine invariant, then, after the appropriate renormalization, its associated function satisfies the following condition:
\begin{equation}\label{eq2032}
F(BAB',Bp,t)=|{\rm det}B|^{1/N}F(A,p,|{\rm det}B|^{1/N}t)
\end{equation}
for any nonsingular linear map $B$.  If a translation invariant
causal scale space $\{T_t\}$ is scale invariant, then, after the
appropriate renormalization, its associated function satisfies for
any $\mu>0$
\begin{equation}\label{eq2033}
F(\mu^2A,\mu p,t)=\mu F(A,p,\mu t).
\end{equation}

\end{lemma}

\begin{proof}
Recall that we have made the blanket assumption that causal spaces
are invariant under the addition of constants. Thus, we assume
that $F$ does not depend on $c$ or $\fxx$. Assume that $B$ is a
linear map and that $\lambda=|{\rm det}B|^{1/N}$. We also assume
that the scale space $\{T_t\}$ is normalized so that
$T_{t+h,t}B=BT_{\lambda(t+h),\lambda t}$. Let $u$ be a quadratic
function around 0, $u(\fxy)=(1/2)\langle A\fxy,\fxy\rangle+\langle
p,\fxy\rangle$. Then
\[
T_{t+h,t}[u(B\fxy)](0)=T_{\lambda(t+h),\lambda t}u(B0)=T_{\lambda(t+h),\lambda t}u(0).
\]
Since $u(B'\fxy)=(1/2)\langle BAB'\fxy,\fxy\rangle+\langle
Bp,\fxy\rangle$ around 0 and by the regularity of $\{T_t\}$,
\[
T_{t+h,t}[u(B'\fxy)](0)=hF(BAB',Bp,t)+o(h).
\]
Also by regularity
\[
T_{\lambda(t+h),\lambda t}u(0)=\lambda hF(A,p,\lambda t)+o(\lambda h).
\]
Thus we have $hF(BAB',Bp,t)+o(h)=\lambda hF(A,p,\lambda t)+o(\lambda h)$. Dividing by $h$ and letting $h\to0$ proves the first part of the lemma. To prove the second part, just replace $B$ with $\mu I$ in the proof of the first part.
\end{proof}

\section{Axiomatic approach to linear scale space}

We are going to use previous results from this chapter, in
particularly Theorem \ref{theorem17.8}, to characterize the heat
equation $\partial u/\partial t=\Delta u$ as the unique scale
space that is both linear and isotropic. A consequence for image
processing is that linear smoothing and contrast-invariance
 are incompatible. (Recall that we showed in Section
 \ref{section2.3}
that the heat equation was not contrast invariant. This is
illustrated numerically in Figure
\ref{heateqnnotcontrastinvariant}.)  At some level,
 this explains
the coexistence of at least two different schools of image
processing: contrast-invariant mathematical morphology on the one
hand, and classical linear scale space on the other, which is
essentially convolution with the Gaussian (Theorem
\ref{theorem2.3}).

\begin{theorem}\label{theorem17.22}Let $\{T_t\}$ be a translation-invariant, causal,
 isotropic
and linear scale space on $\mathcal F$. Then
$F(D^2u,Du,t)=c(t)\Delta u$, where $c(t)\geq0$. If, in addition,
$F$ is assumed to be continuous in $t$, then up to a rescaling
$t'=h(t)$, the function $u(t,\fxx)=T_tu_0(\fxx)$ is a viscosity
solution of the heat equation
\begin{equation}\label{eq2042}
\frac{\partial u}{\partial t}(t,\fxx)=
\Delta u(t,\fxx),\quad (t,\fxx)\in[0,\infty)\times\RR^N.
\end{equation}
\end{theorem}

\begin{figure}[!t]
\setkeys{Gin}{width=10cm}
\centerline{
\includegraphics{fig17.05.1.eps}
} \caption[The heat equation is not contrast invariant]{The heat
equation is not contrast invariant.   First row: original image.
Second row: Two different contrast changes have been applied to
this image. Third row: A convolution by a Gaussian is applied  to
both images of the second row. Fourth row: The inverse contrast
change is applied to the images of the third row. If the linear
scale space were contrast invariant, these images should be equal.
This is not the case, since the difference (displayed in the fifth
row) is not null.\label{heateqnnotcontrastinvariant}}
\end{figure}

\begin{proof}
Since the scale space is translation invariant, $F$ does not
depend on $\fxx$ (Proposition \ref{proposition17.13}), and since
the scale space commutes with the addition of constants, $F$ does
not depend on $c$ (Proposition \ref{proposition17.10}). Thus,
$F(A,p,\fxx,c,t)=F(A,p,t)$. We know from Theorem \ref{theorem17.8}
that $T_{t+h,t}u(\fxx)-u(\fxx)=hF(D^2u(\fxx),Du(\fxx),t)+o(h)$ for
any $u\in C^2(\RR^N)$. Since $T_{t+h,t}$ is linear, we have
$T_{t+h,t}(ru+sv)=rT_{t+h,t}u+sT_{t+h,t}v$ for any $u,v\in
C^2(\RR^N)$ and $r,s\in\RR$. This and Theorem 17.8 imply that
\[
F(D^2(ru+sv),D(ru+sv),t)=rF(D^2u,Du,t)+sF(D^2v,Dv,t),
\]
which means that $F$ is linear in the argument $u$. (In what
follows, we keep $t$ fixed, and for convenience we write $F(A,p)$
rather than $F(A,p,t)$.) We can choose any values for $D^2u, D^2v,
Du,$ and $Dv$. Thus we have
\[
F(rA+sA', rp+sp')=rF(A,p)+sF(A',p')
\]
where $A$ and $A'$ are arbitrary symmetric matrices and $p$ and
$p'$ are arbitrary vectors. From this, we see that
$F(A,p)=F(A,0)+F(0,p)$. Now define $F_1$ and $F_2$ by
$F_1(p)=F(0,p)$ and $F_2(A)=F(A,0)$; $F_1$ and $F_2$ are clearly
linear. Using the assumption that the operators are isotropic
$T_{t,s}$, we see from Lemma \ref{lemma17.15} that
\[
F_1(p)+F_2(A)=F_1(Rp)+F_2(RAR'),
\]
where $R$ is any linear isometry of $\RR^N$. Taking $A=0$, this
implies that $F_1(Rp)=F_1(p)$ for any linear isometry $R$. Since
$F_1$ is linear, this implies that $F_1$ is a constant. Since by
Proposition \ref{proposition17.10} $F(0,0,t)=0$, we conclude that
$F_1(p)=0$. This proves that $F(A)=F(RAR')$, where $A$ is an
arbitrary $N\times N$ symmetric matrix and $R$ is an arbitrary
linear isometry.

Given any symmetric matrix $A$, there is a linear isometry $R$ such that $RAR'$ is diagonal whenever the coordinate system is orthogonal. Furthermore, any two  diagonalizations differ only in the arrangement of the diagonal entries, which are the $N$ eigenvalues of $A$, and any arrangement of these entries can be achieved by some linear isometry. This means that the value of $F(A)$ depends only on some symmetric function $f$ of the eigenvalues $\lambda_1,\lambda_2,\dots\lambda_N$ of $A$.  That means that $F(A)=F(f(\lambda_1,\lambda_2,\dots\lambda_N))$, where $f$ is a symmetric function of its arguments. Since $F$ is also linear, we have
\[
F(f(r\lambda_1,r\lambda_2,\dots r\lambda_N))=rF(f(\lambda_1,\lambda_2,\dots\lambda_N)).
\]
Since the only linear symmetric function of $N$ variables is, up to a multiplicative constant, the linear function, we see that
\[
F(A)=c\,{\rm trace}(A)
\]
for some constant $c$. Since $F$ is nondecreasing  in $A$ (Lemma
\ref{lemma17.7}), $c$ is nonnegative. We conclude that
$F(D^2u,Du)=c\Delta u$. Remember that this argument has been made
with a fixed $t$ that was not written. Thus, our real conclusion
is that $F(D^2u, Du, t)=c(t)\Delta u$, where $c$ is a nonnegative
function of $t$.

If we assume that $F$ is  continuous in $t$, then $t\mapsto c(t)$
is continuous. Then by Theorem \ref{theorem17.11},
$u(t,\fxx)=T_tu_0(\fxx)$ is a viscosity solution of
\[
\frac{\partial u}{\partial t}(t,\fxx)=c(t)\Delta u(t,\fxx).
\]
Finally, if we rescale using the function $t\mapsto t'$ defined by $\partial t'\partial t(t)=c(t)$, we have the heat equation $\partial u/\partial t'=\Delta u$.
\end{proof}


\section{Exercises}
\begin{exercise} \label{exerciserescalingscalespace}
 Let $T_t$ be a causal scale space (Definition \ref{definition17.6})
  and $h:\RR^+\to \RR^+$  a $C^2$ increasing function. Prove that
  that $S_t=T_{h(t)}$ also is a causal scale space. Assume that $T_t$ is scale invariant
  and let $t'(t,\lambda)$ its rescaling function.  Compute $t'$ for  the new scale space
  $S_t$. \finex
\end{exercise}

\begin{exercise}Consider the extrema killer $T_t$ defined in
section \ref{section6.4}, where $t$ denotes the area threshold.
Show that the family $\{T_t\}$ is pyramidal and satisfies the
global comparison principle, but that it does not satisfy the
local comparison principle. Show that the family is, however,
regular at $t=0$ and, more precisely, that
\[
F(A,p,0)=0\quad\text{if $p\not=0$}.
\]
 Check the other invariance
properties of the extrema killer : prove in particular that it is
affine invariant and compute $t'(t,\lambda)$ (Definition
\ref{definition17.18}). \finex
\end{exercise}

\begin{exercise} Let $g$ be an integrable continuous function
 and for $u\in  \mathcal F$, $Tu=g\ast u$. Prove that $T$ is
 translation  invariant and isotropic. \finex
\end{exercise}

\begin{exercise}Define   $\{T_t\}$ by
$T_tu_0=g_t*u_0$, where $g_t(\fxx)=\frac 1{t^2}g(\frac{\fxx}{t})$.
Prove that $\{T_t\}$ is scale invariant (Definition
\ref{definition17.18}) and compute the function $t'(t,\lambda)$.
Same questions if we set $g_t(\fxx)=\frac
1{t}g(\frac{\fxx}{t^\frac 12}).$ \finex
\end{exercise}

\begin{exercise}\label{exerciseclassicalscalespaces} Check
that Definition \ref{definition17.18} is valid for the classical
scale spaces we already know: For the morphological operators,
dilation and erosion, show that $t'(t,\lambda)=\lambda t$, no
matter what the structuring element $B$ is. Prove that these
operators are not affine invariant. For the heat equation and mean
curvature motion, check that $t'(t,\lambda)=\lambda^2 t$. \finex
\end{exercise}

\section{Comments and references}
The presentation in this chapter  and the next one follows
essentially the work of L. Alvarez, F. Guichard, P.-L. Lions, and
J.-M. Morel in \cite{Alvarez:1993:AFE}, \cite{Alvarez:1992:ANO},
and \cite{Alvarez:1992:AEF}. Their stated objective was to ``...
describe all multiscale causal, local, stable and shape preserving
smoothing operators. This classification contains the classical
`morphological' operators, and some new ones.'' This axiomatic
approach is presented in several survey papers, with increasingly
simple sets of axioms: Lions \cite{Lions:1994:ADI}; Alvarez and
Morel \cite{Alvarez:1999:FCA}; Guichard, Lopez, and Morel
\cite{Guichard:1995:AVP}; and Guichard's doctoral thesis
\cite{Guichard:1994:AAM}, which was an early version of this book.


\paragraph*{Linear scale space.}
Scale space theory was founded (in the linear framework) by Witkin
\cite{Witkin:1983:SSF}, Marr \cite{Marr:1982:V}, and Koenderink.
An earlier development of linear scale space has been traced to
Japan in \cite{Weickert:1997:HGS,Weickert:1999:LSS}. Many works by
Florack, ter Haar Romeny, Koenderink, and Viergever focus on the
computation of partial derivatives of any order of an image and
their use in image analysis
\cite{Florack:1992:FTS,Florack:1992:SDS,Florack:1993:MLJ,Florack:1994:LSS}.
The concept of {\em causality}, used by all of these authors is
crucial; it has been reinterpreted in this chapter as the
combination of two  requirements: a pyramidal structure and a
comparison principle. De Giorgi founded his mathematical theory of
barriers for geometric motions on similar principles
\cite{Giorgi:1995:NCF}. There are many axiomatic characterizations
of linear scale space in terms of causality, invariants, and
conservation properties. We mention particularly the early work by
Babaud, Witkin, Baudin, and Duda \cite{Babaud:1986:UGK} and Hummel
\cite{Hummel:1988:SSF}. A slight relaxation of the initial axioms
led Pauwels and others to discover other possible linear scale
spaces, which, however, are less local \cite{Pauwels:1995:ECS}.
There have also been several attempts to define nonlinear scale
spaces, which are understood as nonlinear invariant families of
smoothing operators. In mathematical morphology, we mention work
by Chen \cite{Chen:1989:MAB}, Toet
\cite{Toet:1989:MPI,Toet:1990:HMI}, and Jackway
\cite{Jackway:1996:SSP}; Jackway emphasized the scale space
properties of multiscale erosions and dilations. After the
publication of \cite{Alvarez:1993:AFE} by Alvarez, Guichard,
Lions, and Morel, several different axiomatic approaches have been
proposed for nonlinear scale spaces. Weickert insists on grey
level conservation, which excludes all of the mathematical
morphology operators, and proposes a line of conservative
parabolic nonlinear PDEs
\cite{Weickert:1996:TFA,Weickert:1998:ADI}. The axiomatic
presentation of Olver, Sapiro, and Tannenbaum
\cite{Olver:1994:DIS} deduces the various scale spaces as
invariant heat flows. See also \cite{Niessen:1997:GFG}; the book
\cite{Romney:GDD} contains miscellaneous contributions to
geometric diffusion.

\paragraph*{Extensions.}
 Caselles, Coll, and Morel have questioned the very soundness of
 applying any of the proposed scale spaces to natural images
 \cite{Caselles:1996:PDE}. They argue following the Kanisza
 psychophysical theory that occlusions generate T-junctions in
 images and that these T-junctions should be detected before any
 smoothing is applied (see Figure \ref{tjunctions}.) In \cite{Caselles:1997:SSV}, the same
 authors propose the set of level lines of the image, the
 so-called topographical map, as an alternative multiscale
 structure for describing images. In another direction,
  Geraets and others proposed a
 generalization of scale space to discrete point sets
 \cite{Geraets:1995:ASS}.

\paragraph*{Contrast invariance.}
 The Wertheimer principle, which states that human visual perception is independent of
changes in illumination, was enunciated in 1923
\cite{Wertheimer:1923:ULG}. Contrast invariance appears in
mathematical morphology in the work of Serra
\cite{Serra:1988:IAM}. Koenderink and van Doorn emphasized this
requirement and introduced photometric invariants
\cite{Koenderink:1980:PIR}. Florack and others studied
contrast-invariant differential operators in
\cite{Florack:1994:GIT}. Romeny and others construct third-order
contrast-invariant operators to detect T-junctions
\cite{Romeny:1991:ITO}. See also \cite{Rahmati:1994:IID}. The
significance of contrast invariance for smoothing T-junctions is
illustrated in Figure \ref{tjunctions}.



\paragraph*{Rotation and scale invariance.}
One of the first discussions of rotation-invariant image operators
was given by Beaudet in \cite{Beaudet:1978:RII}. See also Lenz
\cite{Lenz:1986:RIO} for work on rotation-invariant operators.
Scale-invariant shape representation is discussed by Baldwin,
Geiger, and Hummel in \cite{Baldwin:1998:RAS}. Alvarez, Gousseau,
and Morel use numerical experiments on natural images to confirm
their scale invariance \cite{Alvarez:1999:SNI}.

\paragraph*{Affine invariance.}
Affine invariants are viewed as approximate projective invariants
by Chang in \cite{Cheng:1996:AAI}. The importance of affine
invariance for three-dimensional object recognition is discussed
in \cite{Baldwin:1998:RAS} and \cite{Lenz:1986:RIO}. Work by
Forsyth, Munday, and Zisserman has been fundamental and has
launched wide-ranging discussion of this theme
\cite{Forsyth:1992:TIP,Mundy:19xx:GIC,Mundy:1994:AIC}. Further
contributions to the use and computation of affine and projective
differential invariants in image processing can be found in
\cite{Blom:1992:AIC}, \cite{Salden:1993:APD},
\cite{VanGool:1992:SDI}, and \cite{Weiss:1995:LPA}.



\newpage

\begin{figure}[!ht]
\setkeys{Gin}{width=10cm}
\centerline{
\includegraphics{fig17.07.1.eps}
} \caption[Contrast invariance of AMSS]{Contrast invariance of the
affine morphological scale space (AMSS). First row: original
image. Second row: two contrast changes applied to the original.
Third row : AMSS applied to both images of the second row, by a
finite difference scheme. Fourth row: inverse contrast change
applied to the filtered images. A visual check shows that they are
almost identical. Bottom image: numerical check by taking the
difference of the images in the fourth row. Compare this with the
same experiment performed with the linear scale space, Figure
\ref{heateqnnotcontrastinvariant}.\label{amssiscontrastinvariant}}
\end{figure}


\begin{figure}[!ht]
\setkeys{Gin}{width=10cm}
\centerline{
\includegraphics{fig17.06.1.eps}
} \caption[Same geometric figures, different evolutions under
smoothing] {Same geometric figures, different evolutions under
smoothing. 1st row: The four figures have T-junctions that differ
in the way grey levels are distributed among the three regions. In
the first two figures, the grey levels are monotone in, say, the
clockwise direction. This means that they differ by a monotone
contrast change. The same is true for the second two figures.
However, the first and third figures differ by a nonmonotone
contrast change. 2nd row: result of a smoothing by the AMSS model.
We see that
two different evolutions are possible: If the regions of the image
keep the same order of grey levels, then the geometric evolution
is identical. If, instead, a nonmonotone contrast change has been
applied, the evolutions are geometrically different. \\ 3rd row:
result of a smoothing by the linear scale space. All four
T-junctions give different evolutions. The evolution depends on
the gray-level values of the three level sets, rather than
depending only on their order. \\ 4rd row: quantization of the 3rd
row to display the shapes of some level lines.\label{tjunctions}
}
\end{figure}



\begin{figure}[!ht]
\setkeys{Gin}{width=9cm}
\centerline{
\includegraphics{fig17.03.1.eps}
} \caption[Hyperdiscrimination of textures by nonlinear scale
space]{ Hyperdiscrimination of textures by nonlinear scale space.
According to the Julesz theory of textons, human perception can
discriminate different textures if their average behavior in terms
of ``texton'' density is different. As shown in its mathematical
formalization, proposed by C. Lopez, some of the texton densities
can be interpreted as densities of the positive and negative parts
of the image curvature at different scales. In this remarkable
experiment, C. Lopez proved that one of the simplest
contrast-invariant scale spaces beats by far the human
discrimination performance. From left to right and top to bottom:
1-an original texture pair that is preattentively undiscriminable.
The central  square of the image consists of rotated ``10's'' and
the rest of the image of rotated ``S's.''  These patterns are
different, but have the same number of bars, angles, and so forth.
2-curvature motion applied to the original up to some scale
3-negative part of the curvature at the same scale 4-positive part
of the curvature at the same scale 5-multichannel segmentation of
the multi-image made of the curvatures 6-negative part of the
curvature at scale 0. As seen in 2, 3, 4 and 5, this nonlinear
scale space easily discriminates between the two textures.
\label{Julesz} }
\end{figure}


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