%gmChap17.tex

\graphicspath{{./figures/chapter17/}}

\chapter{Scale Spaces and Partial Differential Equations\label{ChapSSPDE}}

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

\begin{definition}A {\em scale space} is a family of image (function) operators $\{T_t\}$, $t\in\RR^+$, defined on a domain of functions $u:\RR^N\to\RR$.
\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 17.5. 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}

The first order of business is to say something about the domain and range of the operators $T_t$ belonging to a scale space $\{T_t\}$. Our approach requires that these operators are defined on all quadratic function from $\RR^N$ to $\RR$. With this in mind, we are going to assume that the $T_t$ are defined on all continuous functions that grow no faster than some polynomial. Formally, $u$ is in the domain of $T_t$ if there is a constant $C$ and a positive integer $n$ such that
\begin{equation}\label{eq20a}
|u(\fxx)|\leq C(1+|\fxx|^n).
\end{equation}
We also assume that the $T_tu$ satisfy this kind of condition.

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}A scale space $\{T_t\}$ is said to be {\em pyramidal} if there is another family of operators $\{T_{t+h,t}\}$, $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 17.20, which is a key result in our program. We assume that the transition operators have the same domain and range as the $T_t$. This means that they are defined on functions that satisfy \eqref{eq20a} and they return functions that satisfy \eqref{eq20a}.

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

\begin{definition}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}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)<v(\fxy)$ for $\fxy$ in some neighborhood of $\fxx$, $\fxx\not=\fxy$, 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. (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}Assume that $u$ is a quadratic function defined for $\fxy\in\RR^N$ and represent $u$ as
\[
u(\fxy)=\frac1{2}\langle A(\fxy-\fxx),\fxy-\fxx\rangle +\langle p,\fxy-\fxx\rangle+c,
\]
where $A=D^2u$ is an $N\times N$ matrix, $p=Du$ is a vector in $\RR^N$, and $c=u(\fxx)$ is a constant. 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
\begin{equation}\label{eq204}
\frac{T_{t+h,t}u(\fxx)-u(\fxx)}{h}\to F(A,p,\fxx,c,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)$, since 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 2.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.

\begin{definition}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}

An immediate consequence of this definition is that the function $F$ is nonincreasing in its first variable. This is the first of several properties of $F$ that will follow from assumptions about the scale space $\{T_t\}$.

\begin{lemma}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. Define $Q_A$ and $Q_B$ 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$,  $Q_A(\fxy)\leq Q_B(\fxy)$. Use the second part of the local comparison principal (monotonicity) to conclude that $T_{t+h,t}Q_A(\fxx)\leq T_{t+h,t}Q_B(\fxx)$ for all $\fxx\in\RR^N$. 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.

\begin{exercise}Consider the extreme killer $T_t$ defined in section 6.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$}. \finex
\]
\end{exercise}

\section{Causal scale spaces are governed by PDEs}

The next result, Theorem 17.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}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}The regularity assumption means that there is a function $F$, which is continuous in its first argument, such that
\[
\frac{T_{t+h,t}v(\fxx)-v(\fxx)}{h}\to F(A,p,\fxx,c,t)\quad\text{as}\quad h\to0
\]
for any quadratic function
\[
v(\fxy)=\frac1{2}\langle A(\fxy-\fxx),\fxy-\fxx\rangle +\langle p,\fxy-\fxx\rangle+c.
\]
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^-$ 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|$, $\fxx\not=\fxy$,
\[
Q^-(\fxy)<u(\fxy)< 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)\leq T_{t+h,t}u(\fxx)\leq T_{t+h,t}Q^+(\fxx)
\]
for sufficiently small $h$. Since $Q^-(\fxx)=u(\fxx)= Q^+(\fxx)$, we have
\[
T_{t+h,t}Q^-(\fxx)-Q^-(\fxx)\leq T_{t+h,t}u(\fxx)-u(\fxx)\leq T_{t+h,t}Q^+(\fxx)-Q^+(\fxx).
\]
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}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}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 the quadratic function
$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 17.5).

\begin{theorem}Assume that the 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 18.10, it is sufficient to prove \eqref{eq2015}.)

On the basis of Lemma 15.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 17.10). This section is devoted to continuing this program: Assume an invariant for $\{T_t\}$ and deduce its implication for $F$. There are two steps: defining the invariant and deducing its implications.

\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 6.4 using the translation operator $\tau_{\fxz}$: $\tau_{\fxz}u(\fxx)=u(\fxx-\fxz)$ for all $\fxx,\fxz\in\RR^N$.

\begin{definition}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}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 the two quadratic functions $u$ and $\tau_{\fxx}u$ 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}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 the 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}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 $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}


We can summarize this section by saying that if a causal scale space $\{T_t\}$ is invariant under Euclidean motions (including reflections), then the associated function $F$ is also invariant under these motions, in the sense that $F$ does not depend on $\fxx$ (translations) and $F(A,p,t)=F(RAR',Rp,t)$ for all orthogonal matrices $R$ (rotations and reflections).

\subsection{Contrast invariance}

\begin{definition}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 17.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}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}The assumption is that $g\circ T_{t+h,t}=T_{t+h,t}\circ g$ for any nondecreasing continuous function $g$, but to prove the lemma, we need only to assume that this is true for $g$ that are $C^2$. The arbitrary parameters $\lambda$ and $\mu$ will be associated with $g$ as follows: $g'(0)=\mu$ and $g''(0)=\lambda$. The proof depends on the fact that we can choose a $C^2$ contrast change $g$ with arbitrary values for $g'(0)\geq0$ and $g''(0)\in\RR$. Although we have used the notation before, recall that $p\otimes p$ denotes the $N\times N$ matrix whose entries are $p_ip_j$, $i,j\in \{1,2,\ldots,N\}$. Here are two more preliminaries: Given a $C^2$ function $u$, 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}

We can now begin. Choose any quadratic function of the form
\[
u(\fxy)=(1/2)\langle A\fxy,\fxy\rangle+\langle p,\fxy\rangle.
\]
(We have taken $\fxx=0$ without loss of generality based on the assumption that $\{T_t\}$ is translation invariant.) 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
\[
\mu F(A,p,t)=F(\mu A+\lambda p\otimes p, \mu p,t),
\]
which is what we wished to prove.
\end{proof}

\subsection{Scale and affine invariance}

The invariants we have considered can be classified according to the nature of the transformations under which the scale space is invariant. In the case of contrast invariance, the transformation $u\mapsto g(u)$ involves the range of the function. The other invariants have been defined by mappings of the domain of $u$. In fact, we have considered all of the mappings of $\RR^N$ into $\RR^N$ that preserve distance: translations, rotations, and reflections. In this section, we study invariants defined by mappings of $\RR^N$ that do not necessarily preserve distance. Specifically, we consider all linear mappings $A:\RR^N\to\RR^N$, where the matrix $A$ has nonzero determinant. The simplest of these mappings is given by $\fxx\mapsto\lambda\fxx$, $\lambda>0$. This generates a transformation of the real-valued functions $u$ defined on $\RR^N$, which we denote by $H_\lambda$. Thus, $H_\lambda u(\fxx)=u(\lambda\fxx)$.

The main purpose of this section is to established a normalized link between scale $(t)$ and space $(\fxx)$. This is the content of Lemma 17.20. We consider families of function operators $\{T_t\}$, $t\geq0$; they are scale spaces, but they are not necessarily pyramidal. At the abstract level they are not necessarily smoothing operators, but it will be handy to think of them as smoothing operators. We always assume that the mapping $t:[0,\infty)\mapsto T_t$ is one-to-one. (We do not want the scale space to be cyclic.) In fact, we need no other assumptions about the family $\{T_t\}$, except the scale-invariance assumptions given in Definitions 17.18. Thus, the results will be true for any scale-invariant family of operators  $\{T_t\}$, where $t\in\RR^+$. The consequences of the normalization between scale and space are therefore wide-ranging. The general principle is that ``the relation between scale and space can be normalized,'' and more precisely, normalized so $t'=\lambda t$, where $t$ is the scale parameter before ``zooming'' by the factor $\lambda$, and $t'$ is the smoothing scale after ``zooming.''

\begin{definition}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}, in fact, implies condition \eqref{eq2027}, and is thus a slightly stronger assumption. It has the advantage of making our classification of scale-invariant scale spaces easier. We will see, however, that condition \eqref{eq2027} is sufficient to prove that the function $t':(t,\lambda)\mapsto t'(t,\lambda)$ can be normalized. (This can be seen by checking the proof of Lemma 17.20, which uses only condition \eqref{eq2027} and its extension condition \eqref{eq2028}.) We cannot fix a priori the form of $t'$, since it can vary in specific examples of scale spaces. We can, however, normalize it, which means that we can always rescale a scale-invariant scale space so $t'=\lambda t$.

Scale invariance means that the result of applying a scale-invariant scale space $\{T_t\}$ is 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 at therefore at vary different scales (see Figure \ref{mutiscaleworld}). It is thus essential for the stability of shape analysis that the result of an analysis of an object not yield different ``shapes'' at different distances. The sequence of shapes obtained by scale space must be independent of the (a priori unknown) size of the object. Of course, we cannot impose the condition $t'=t$, since the scale of smoothing and the scale of the image are covariant, as can be appreciated by considering linear filtering and 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 increase. Informally, we can say that the scale of analysis increases with the size of the picture. This is a natural assumption that is satisfied by all the classical models. The continuity and differentiability assumptions about $t'$ are also satisfied by the classical models and seems natural. It is easy to determine the function $t'$ for several classical scale spaces. For the morphological operators, dilation and erosion, it is clear that $t'(t,\lambda)=\lambda t$, and for the heat equation and mean curvature motion we have $t'(t,\lambda)=\lambda^2 t$.

The next definition (axiom) introduces an invariant that implies both isotropic and scale invariance; it also means that the scale space is invariant under any orthographic projection of a planar shape. Combining these invariants leads to an arbitrary nonsingular transformation $A$ of the plane. We write $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 this physical and perceptual phenomena by defining a smoothing at different scales that eliminates the finer structures at a scale $t$, but minimally modifies the image at scales above $t$.
\label{mutiscaleworld}}
\end{figure}


\begin{definition}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 independent of the distance and orientation in space of the analyzed planar image. Indeed, any affine map $u\mapsto Au$ can be thought of as the anamorphosis of a planar image $u$ as it is presented to the eye at any distance sufficiently large with respect to its size and with an arbitrary orientation in space. (Recall that an affine transformation is a projective transformation with the ``focal point'' at infinity.)

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, without loss of generality, assume that scale-invariant scale spaces have the same scale-space function, namely $t'=\lambda t$. This is so because we can by Lemma 17.20 renormalize the scale space. On the other hand, it may be more convenient to use a different normalization, say, $t'=\lambda^2 t$ in the case of a linear scale space. We will see, in the process of identifying all scale spaces having certain invariants, that the next lemma is an essential tool. This is because the scale spaces fall into equivalence classes, where all members of a given class differ only by a rescaling. Thus, we use the phrase ``up to a rescaling.''

\begin{lemma}[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 the operators $S_t$ are defined by $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)$. The first step is to show 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}.

The second step is to show that the function $t'$ is increasing with respect to $t$. 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$. The conclusion is that $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; we have just shown that it is also one-to-one and the $t'(0,A)=0$. Said another way, $t'\mapsto t'(t,A)$ is a homeomorphism of $[0,\infty)$ onto $[0,\infty)$ for every $A$ with nonzero determinant. It is then an easy exercise to show that $t'$ is increasing in $t$: If this were not the case, there would be $0\leq s<t$ such that $t'(s,A)\geq t'(s,A)$. Then there is an $r$, $0\leq r<s$ such that $t'(r,A)= t'(t,A)$, which contradicts the fact that $t'$ is one-to-one.

Let $R$ be an orthogonal matrix. The third step is to show that
\begin{equation}\label{eq2037}
t'(t,R)=t.
\end{equation}
Define $t_1=t'(t,R)$ and $t_{n+1}=t'(t_n,R)$. From \eqref{eq2034} we see that $t_{n}=t'(t,R^n)$. There are three cases to consider: (1) $t_1=t$; (2) $t_1<t$; (3) $t_1>t$. If case (1) holds, then we have \eqref{eq2037} and are done. In case (2), the fact that $t'$ is strictly increasing in $t$ implies that the sequence $t_n$ is strictly decreasing. Similarly, in case (3), the sequence $t_n$ is strictly increasing. If $R^m=I$ for some $m\not=0$, then the sequence $t_n$ is periodic and $t_{m+1}=t_1$. In case (2), this implies that $t_{m+1}<t_1$ and $t_{m+1}=t_1$, which is impossible. Similarly, case (3) is untenable. Consequently, if $R^m=I$ for some $m\not=0$, then cases (2) and (3) must be rejected and case (1) holds, which means that \eqref{eq2037} is true. In particular, $t'(t,I)=t$. To continue, we assume that $R^n\not=I$ for $n>0$. 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 both cases (2) and (3), this leads to the contradiction that $t<t$: In case (2), we have $t=\lim_{k\to\infty}t'(t,R^{m_k})<t$, and in case (3) we have $t=\lim_{k\to\infty}t'(t,R^{m_k})>t$. Once again, cases (2) and (3) are untenable, and case (1) must be true.

The next 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)$. The conclusion is that
\begin{equation}\label{eq2037a}
t'(t,B)=t'(t,|{\rm det}B|^{1/N})
\end{equation}
for all transforms $B$ that have nonzero determinants.

We turn now to the rescaling problem. We wish to find 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$. 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}$.

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}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}(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 the following condition:
\begin{equation}\label{eq2033}
F(\mu^2A,\mu p,t)=\mu F(A,p,\mu t)
\end{equation}
for any $\mu>0$.
\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 the quadratic function defined by
$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$ 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 17.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-invariant smoothing are incompatible. (Recall that we showed in section 2.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 2.3).

For our axiomatic approach, we require that the scale spaces are defined on quadratic functions. Since we are working with the heat equation, this means that we need to extend the work done in Chapter 1. We showed there that $u(t,\fxx)=G_t*u_0(\fxx)$, where $G$ is the Gaussian, was a classical solution of the heat equation when $u_0$ was in $L^1_C$, which means that $u_0$ was $C$-periodic and integrable on $C=[-1,1]^N$ (Theorem 1.10). We wish to extend this result to include quadratic functions, and, more generally, functions that grow no faster at infinity than a polynomial. This is the content of the next exercise.

\begin{exercise}Let $u_0$ be a measurable function defined on $\RR^N$ having the property that there exist a constant $C>0$ and an integer $k$ such that
\[
|u_0(\fxx)|\leq C(1+|\fxx|^k)
\]
for all $\fxx\in\RR^N$. Show that the function $u$ defined by $u(t,\fxx)=G_t*u_0(\fxx)$ is well defined and $C^\infty$ on $(0,\infty)\times\RR^N$ and that it is a classical solution of the heat equation. Hints: Everything follows from the fact that the Gaussian and all of its derivatives decay exponentially at infinity.  Various propositions leading to Theorem 1.10 are quickly extended to the case at hand. Finally, note that there is no question here of uniqueness; we only need the fact that $u=G*u_0$ satisfies the heat equation. \finex
\end{exercise}

\begin{theorem}Let $\{T_t\}$ be a translation-invariant causal scale space. Assume that $\{T_t\}$ is defined on a family of functions $\mathcal F$ that has the following property $\mathcal P$: For each $\fxx\in\RR^N$, each $p\in\RR^N$, and each $N\times N$ symmetric matrix $A$, there exists a function $u\in\mathcal F$ such that $Du(\fxx)=p$ and $D^2u(\fxx)=A$. If the operators $T_{t,s}$ are linear and isotropic $($Euclidean invariant$)$, 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. This experiment shows that the linear scale space 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 17.13), and since the scale space commutes with the addition of constants, $F$ does not depend on $c$ (Proposition 17.10). Thus, $F(A,p,\fxx,c,t)=F(A,p,t)$. We know from Theorem 17.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)$.) Since $\mathcal F$ satisfies property $\mathcal P$, we can choose any values, including zero, 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 17.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 17.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 17.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 17.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}

If $u$ happens to be in $C^2(\RR^+\times\RR^N)$, then we know from Proposition 15.7 that $u$ is a classical solution of the heat equation.

\begin{exercise}Define the linear scale space $\{T_t\}$ by $T_tu_0=G_t*u_0$, where $G$ is the Gaussian. Prove that $\{T_t\}$ is scale invariant (Definition 17.18); in particular, show that for $\lambda>0$, $H_\lambda T_{t'}=T_tH_\lambda$ with $t'=t\lambda^2$. Prove that the scale space is also isotropic in the sense that $T_tR=RT_t$ for any linear isometry $R$ of $\RR^N$. Hint: Show that $G_t(R\fxx)=G_t(\fxx)$. \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 \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. 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. Geraets and others propose 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}
