%gmChap18.tex

\graphicspath{{./figures/chapter18/}}

\chapter{The Contrast-Invariant and Affine-Invariant Scale Spaces\label{ChapTCIAAISS}}

This chapter is a direct continuation of Chapter 17. We are going to characterize, up to a multiplicative constant, all of the contrast-invariant scale spaces as \textit{curvature evolution equations}. In the interest of simplicity and clarity, we will first prove the result in two dimensions. The computations are more intuitive in this case, and they are easily displayed in detail. The results are generalized to any dimension in section 18.2.

\section{The two-dimensional case} We will show that if a scale space $\{T_t\}$ is causal, isometric, and contrast invariant, then the associated PDE is of the form
\begin{equation}\label{eq211}
\frac{\partial u}{\partial t}=|Du|G({\rm curv}(u),t).
\end{equation}
This does not tell us much about $G$, so the question is, What additional assumptions must be made to have a more specific characterization of $G$? One answer is this: If we assume that $\{T_t\}$ is affine invariant and that $T_t(-u)=-T_tu$ (which we call reverse contrast invariant), then there is only one equation that satisfies all of these condition, namely, the so-called affine morphological scale space (AMSS),
\[
\frac{\partial u}{\partial t}=|Du|({\rm curv}(u))^{1/3}.
\]

We are led by Theorem 17.8 to study scale spaces defined by PDEs of the form
\[
\frac{\partial u}{\partial t}=F(D^2u,Du,u,\fxx,t),\quad u(0)=u_0,
\]
where $u_0$ is the original image, $u(t,\cdot)$ is the image smoothed at scale $t$, and $F$ is the function associated with $\{T_t\}$. In the two-dimensional case, $A$ is a $2\times2$ symmetric matrix, $p$ is a two-dimensional vector, $c$ is a constant, $\fxx$ is a point in the plane, and $t\in\RR^+$ is the scale. We will be using the following results from Chapter 17:

\begin{enumerate}[$\bullet$]\setlength\itemsep{2pt}
\item If $\{T_t\}$ is translation invariant, then $F$ does not depend on $\fxx$ (Proposition 17.13).
\item It $\{T_t\}$ commutes with the addition of constants, then $F$ does not depend on $c$ (Proposition 17.10).
\item If $\{T_t\}$ is isotropic, then $F(RAR',Rp,t)=F(A,p,t)$ for every $R\in O_2$ (Lemma 17.15).
\item It $\{T_t\}$ is contrast invariant, then $F(\mu A+\lambda (p\otimes p),\mu p,t)=\mu F(A,p,t)$, for any real numbers $\lambda$ and $\mu$, $\mu>0$, any  $2\times2$ symmetric matrix $A$, and any two-dimensional vector $p$ (Lemma 17.17).
Recall that the tensor product $p\otimes p$ is just the symmetric matrix $\{p_ip_j\}$, $i,j\in\{1,2\}$:
\[
p\otimes p=
\begin{bmatrix}
p_1^2&p_1p_2\\
p_1p_2&p_2^2
\end{bmatrix}.
\]
\end{enumerate}

Relations $F(RAR',Rp,t)=F(A,p,t)$ and $F(\mu A+\lambda (p\otimes p),\mu p,t)=\mu F(A,p,t)$ will be used to show that $F$ depends on two real functions $\tilde{a}_{12}$ and $\tilde{a}_{22}$ of $A$ and $p$. These functions are defined by considering the rotation represented by the matrix
\[
R_p=\frac1{|p|}
\begin{bmatrix}
p_1&p_2\\
-p_2&p_1
\end{bmatrix}.
\]
$R_p$ has been chosen to map the unit vector $p/|p|$ onto the unit vector $e_1=(1,0)$:
\begin{equation}\label{eq212}
R_pp=|p|e_1.
\end{equation}
The functions $\tilde a_{ij}$, $i,j\in\{1,2\}$, are defined by
\begin{equation}\label{eq213}
\frac1{|p|}R_pAR_p'=
\begin{bmatrix}
\tilde a_{11}&\tilde a_{12}\\
\tilde a_{12}&\tilde a_{22}
\end{bmatrix}.
\end{equation}
A straightforward computation shows that
\begin{align}
\tilde a_{12}&=\frac1{|p|^3}((p_1^2-p_2^2)a_{12}+p_1p_2(a_{22}-a_{11}))=\frac{A(p,p^\perp)}{|p|^3},\label{eq214}\\
\tilde a_{22}&=\frac1{|p|^3}(a_{11}p_2^2-2a_{12}p_1p_2+a_{22}p_1^2)=\frac{A(p^\perp,p^\perp)}{|p|^3}.\label{eq215}
\end{align}

We should keep in mind that $A$ represents $D^2u$ and $p$ represents $Du$ so these results and the calculations that follow, while purely algebraic, have interpretations in differential geometry. In particular,
\begin{align*}
\tilde a_{22}(D^2u,Du)&={\rm div}\Big(\frac{Du}{|Du|}\Big)={\rm curv}(u),\\
\tilde a_{12}(D^2u,Du)&={\rm div}\Big(\frac{Du^\perp}{|Du|}\Big)={\rm anticurv}(u).
\end{align*}

\begin{exercise}This exercise is to give a geometric interpretation of ${\rm anticurv}(u)$. Show that ${\rm anticurv}(u)(\fxx)$ is the curvature of the gradient line of $u$ through the point $\fxx$. The gradient lines are the curves that are tangent to the gradient of $u$ at every point. They form a system of curves that are orthogonal to the level lines of $u$. \finex
\end{exercise}

\begin{lemma}If $F$ satisfies the relations
\begin{align}
F(RAR',Rp,t)&=F(A,p,t),\label{eq21a}\\
F(\mu A+\lambda (p\otimes p),\mu p,t)&=\mu F(A,p,t),\label{eq21b}
\end{align}
then there is a function $G$ of three real variables such that, for $p\not=0$,
\begin{equation}\label{eq216}
F(A,p,t)=|p|G(\tilde a_{12},\tilde a_{22},t).
\end{equation}
\end{lemma}

\begin{proof}We first use \eqref{eq21b} with $\mu=1/|p|$. Thus,
\[
F(A,p,t)=|p|F\Big(\frac{A}{|p|}+\lambda (p\otimes p), \frac{p}{|p|},t\Big),
\]
where $\lambda$ is any real number. Next, we apply \eqref{eq21a} with $R=R_p$:
\begin{align*}
F(A,p,t)&=|p|F\Big(R_p\Big(\frac{A}{|p|}+\lambda (p\otimes p)\Big) R_p',R_p\frac{p}{|p|},t\Big)\\
&=|p|F\Big(R_p\Big(\frac{A}{|p|}\Big)R_p'+\lambda R_p (p\otimes p) R_p', e_1,t\Big).
\end{align*}
It is easily checked that
\[
R_p (p\otimes p) R_p'=
\begin{bmatrix}
|p|^2&0\\
0&0
\end{bmatrix}.
\]
Thus, by \eqref{eq213},
\[
F(A,p,t)=|p|F\Bigg(
\begin{bmatrix}
\tilde a_{11}+\lambda|p|^2&\tilde a_{12}\\
\tilde a_{12}&\tilde a_{22}
\end{bmatrix}, e_1,t\Bigg).
\]
Since $\lambda$ is arbitrary and since $p\not=0$, $F$ depends only on $\tilde a_{12}$ and $\tilde a_{22}$. To finish, we can define $G$ by
\[
G(\tilde a_{12},\tilde a_{22},t)=F\Bigg(
\begin{bmatrix}
0&\tilde a_{12}\\
\tilde a_{12}&\tilde a_{22}
\end{bmatrix}, e_1,t\Bigg). \qedhere
\]
\end{proof}

\begin{lemma}The function $G$ depends only on $\tilde a_{22}$ and $t$.
\end{lemma}

\begin{proof}We will use the fact established in Lemma 17.7 that $F$ is nondecreasing with respect to its first argument and the assumption in Definition 17.5 that $F$ is continuous in this argument. We will also use the result of Lemma 18.1.

Consider two symmetric matrices $A$ and $B$ such that $A\geq B$. In analogy with \eqref{eq213}, we write
\begin{equation}\label{eq213b}
\frac1{|p|}R_PBR_p'=
\begin{bmatrix}
\tilde b_{11}&\tilde b_{12}\\
\tilde b_{12}&\tilde b_{22}
\end{bmatrix}.
\end{equation}
Then
\begin{equation}\label{eq213c}
\frac1{|p|}R_p(A-B)R_p'=
\begin{bmatrix}
\tilde a_{11}-\tilde b_{11}&\tilde a_{12}-\tilde b_{12}\\
\tilde a_{12}-\tilde b_{12}&\tilde a_{22}-\tilde b_{22}
\end{bmatrix}.
\end{equation}
By assumption, the symmetric matrix $A-B$ is such that $A-B\geq0$. This property is invariant under rotation, in particular, under the mapping $A-B\mapsto R_p(A-B)R_p'$. Hence, $A-B\geq0$ if and only if $R_p(A-B)R_p'\geq0$. This means that $A\geq B$ if and only if
\begin{equation}\label{eq217}
(\tilde a_{11}-\tilde b_{11})x^2+2(\tilde a_{12}-\tilde b_{12})xy+(\tilde a_{22}-\tilde b_{22})y^2\geq0
\end{equation}
for all real numbers $x$ and $y$, and this is true if and only if
\begin{equation}\label{eq217a}
(\tilde a_{11}-\tilde b_{11})(\tilde a_{22}-\tilde b_{22})\geq(\tilde a_{12}-\tilde b_{12})^2.
\end{equation}
Fix $A$ and choose an arbitrary $\tilde b_{12},$ $\tilde b_{12}\not=\tilde a_{12}$. Choose any real number $\tilde b_{22}$ such that $\tilde a_{22}-\tilde b_{22}=\varepsilon>0$. Now select $\tilde b_{11}=\tilde b_{11}(\varepsilon)$ so that \eqref{eq217a} is satisfied. Then we have
\[
F\Bigg(
\begin{bmatrix}
\tilde a_{11}&\tilde a_{12}\\
\tilde a_{12}&\tilde a_{22}
\end{bmatrix}, e_1,t\Bigg)\geq
F\Bigg(
\begin{bmatrix}
\tilde b_{11}(\varepsilon)&\tilde b_{12}\\
\tilde b_{12}&\tilde a_{22}-\varepsilon
\end{bmatrix}, e_1,t\Bigg).
\]
The value on the right-hand side of the inequality is independent of $\tilde b_{11}(\varepsilon)$ (Lemma 18.1). Now let $\varepsilon$ tend to zero. By the continuity of $F$ in its first argument, we conclude that
\[
F\Bigg(
\begin{bmatrix}
\tilde a_{11}&\tilde a_{12}\\
\tilde a_{12}&\tilde a_{22}
\end{bmatrix}, e_1,t\Bigg)\geq
F\Bigg(
\begin{bmatrix}
\tilde b_{11}(0)&\tilde b_{12}\\
\tilde b_{12}&\tilde a_{22}
\end{bmatrix}, e_1,t\Bigg),
\]
where $\tilde b_{11}(\varepsilon)\to-\infty$ as $\varepsilon\to0$. This shows that \[
G(\tilde a_{12},\tilde a_{22},t)\geq G(\tilde b_{12},\tilde a_{22},t).
\]
A similar argument shows that
\[
G(\tilde b_{12},\tilde a_{22},t)\geq G(\tilde a_{12},\tilde a_{22},t).
\]
We conclude that $G(\tilde a_{12},\tilde a_{22},t)$ does not depend on $\tilde a_{12}$, and hence that $G$ is a function of only $\tilde a_{22}$ and $t$.
\end{proof}

We summarize these last results in the following theorem.

\begin{theorem}If the two-dimensional scale space $\{T_t\}$ is causal, isometric, and contrast invariant, then its associated PDE has the form
\begin{equation}\label{eq218}
\frac{\partial u}{\partial t}=|Du|G({\rm curv}(u),t),
\end{equation}
where $G$ is continuous and nondecreasing in its first variable.
\end{theorem}

We are now going to introduce scale and affine invariance. We are still working in two dimensions.

\begin{theorem}Assume that the scale space $\{T_t\}$ is causal, isometric, and contrast invariant. In addition, assume that it is scale invariant and that it is normalized according to Lemma 17.20. Then its associated PDE has the form
\begin{equation}\label{eq219}
\frac{\partial u}{\partial t}=|Du|\beta(t{\rm curv}(u)),
\end{equation}
where $\beta$ is continuous and nondecreasing.

If the scale space $\{T_t\}$ is affine invariant and normalized according to Lemma 17.20, then the associated PDE has the form
\begin{equation}\label{eq2110}
\frac{\partial u}{\partial t}=|Du|\beta(t{\rm curv}(u)),
\end{equation}
where $\beta(s)=Cs^{1/3}$ if $s>0$ and $\beta(s)=-D|s|^{1/3}$ if $s<0$, for two    nonnegative constants $C$ and $D$. Conversely, this equation defines an affine-invariant scale space.
\end{theorem}

\begin{proof}By Lemma 17.21, if a causal scale space is affine invariant, then, after appropriate renormalization (Lemma 17.20), its associated function satisfies
\begin{equation}\label{eq2111}
F(BAB',Bp,t)=|{\rm det}B|^{1/2}F(A,p,|{\rm det}B|^{1/2}t)
\end{equation}
for any linear map $B$. If we let $B=cI$, $c>0$, then $F(c^2A,cp,t)=cF(A,p,ct)$. Since $F(A,p,t)=|p|G(\tilde a_{22}(A,p),t)$, this implies that
\[
c|p|G(\tilde a_{22}(c^2A,cp),t)=c|p|G(\tilde a_{22}(A,p),ct),
\]
and since
\[
\tilde a_{22}(c^2A,cp)=\frac{c^2A(cp^\perp,cp^\perp)}{|cp|^3}=c\tilde a_{22}(A,p),
\]
we see that
\[
G(\tilde a_{22}(A,p),ct)=G(c\tilde a_{22}(A,p),t).
\]
Since this equation is true for all $A$, $p\not=0$, $c>0$, and $t>0$, $G(cs,t)=G(s,ct)$ for any $s$ and any positive $c$ and $t$. This implies that \[
G(s,t)=G(st,1)=\beta(st),
\]
where $\beta$ is continuous and nondecreasing. This proves the first part of the theorem.

We now assume that the scale space is affine invariant. To identify the power $1/3$, we need to exploit the affine invariance only in the particular case of ``stretching and shrinking'' along the $x$ and $y$ axes, that is, by using the transformation represented by
\[
B(\lambda)=
\begin{bmatrix}
\lambda&0\\
0&\lambda^{-1}
\end{bmatrix}.
\]
The reason is that any linear transformation of the plane is a product of isometries, magnifications, and ``stretching and shrinking,'' and we have already used isometric invariance and scale invariance. First note that
\[
BAB'=
\begin{bmatrix}
\lambda^2a_{11}&a_{12}\\
a_{12}&\lambda^{-2}a_{22}
\end{bmatrix}\quad\text{and}\quad Bp=(\lambda p_1, p_2/\lambda).
\]
Then we see from \eqref{eq215} that
\begin{equation}\label{eq2112}
\tilde a_{22}(BAB',Bp)=\frac{a_{11}p_2^2-2a_{12}p_1p_2+a_{22}p_1^2}{(\lambda^2p_1^2+\lambda^{-2}p_2^2)^{3/2}}.
\end{equation}
We know that $F(A,p,t)=|p|\beta(t\tilde a_{22}(A,p,t))$. This and the affine-invariance relation \eqref{eq2111} show that
\begin{equation}\label{eq2113}
|Bp|\beta(t\tilde a_{22}(BAB',Bp))=|p|\beta(t\tilde a_{22}(A,p)).
\end{equation}
If we let $p_1=1$, $p_2=0$, and $a_{22}=1$, then from \eqref{eq2112} and \eqref{eq2113} it follows that
\[
|\lambda|\beta(s/\lambda^3)=\beta(s).
\]
The first thing to notice is that $\beta(0)=0$, which is consistent with (and a consequence of) the fact that $F(0,0,t)=0$. On the other hand, nothing we have assumed precludes $\beta(s)=0$ for all $s\geq0$. However, in case $\beta(a)>0$ for some $a>0$, we can select $\lambda>0$ so $\lambda^3=s/a$, and we have
\[
\beta(s)=a^{-1/3}\beta(a)s^{1/3},
\]
in which case $C=a^{-1/3}\beta(a)=\beta(1)$. A similar argument shows that either $\beta(s)=0$ for all $s\leq0$, or
\[
\beta(s)=|b|^{-1/3}\beta(b)|s|^{1/3},
\]
where $D=-|b|^{-1/3}\beta(b)=-\beta(-1)$. The result is thus true in all cases.
\end{proof}

In general, $\beta(1)\not=-\beta(-1)$, that is, $C\not=D$. For example, if $D=0$ and $C>0$, then we have a pure affine erosion (shapes shrink); if $C=0$, then we have a pure affine dilation (shapes expand). However, if the scale space is also \textit{reverse contrast invariant}, which means that $T_{t+h,t}\circ g=g\circ T_{t+h,t}$ for continuous nonincreasing $g$, then $D=C$. To see this, recall the proof of Lemma 17.17. If the scale space $\{T_t\}$ is reverse contrast invariant, then equation (17.16) is true for negative (as well as positive) $\mu$, and we have $F(-A,-p,t)=-F(A,p,t)$. This then implies that $\beta(-1)=-\beta(1)$.

\section{Contrast-invariant scale space equations in $N$ dimensions}

We are going to extend the results of Theorem 18.4 to $N$ dimensions, so we make the same assumptions about the scale space $\{T_t\}$: It is causal, it commutes with the addition of constants, and it is translation invariant. Our immediate aim is to deduce the general form of $F$ in $N$ dimensions from the assumption that $\{T_t\}$ is contrast invariant. If we also assume that $F$ is isometric, then we will show that, for $p\not=0$,
\[
F(A,p,t)=G(\lambda_1,\lambda_1,\ldots,\lambda_{N-1},|p|,t),
\]
where $G$ is a real-valued function defined on $\RR^{N-1}\times (0,+\infty)\times [0,+\infty)$. $G$ is symmetric in the $N-1$ variables $\lambda_1,\lambda_2,\ldots,\lambda_{N-1}$, is positively homogeneous with respect to $\lambda_1,\lambda_2,\ldots,\lambda_{N-1},|p|$, and is nondecreasing with respect to each $\lambda_i$, $1\leq i\leq N-1$ for all $t\in[0,+\infty)$. (In the interest of notation, we will suppress $t$ in the following discussion.)

We know from Lemma 17.17 that the function $F$ associated with a contrast-invariant scale space $\{T_t\}$ satisfies the relation
\begin{equation}\label{eq2114}
F(\mu A+\lambda (p\otimes p), \mu p)=\mu F(A,p)
\end{equation}
for all $\lambda\in\RR$, all $\mu\geq0$, any $N\times N$ symmetric matrix $A\in S^N$, and any vector $p\in\RR^N$. By taking $\lambda=0$, this shows that $F$ is positively homogeneous in $(A,p)$:
\begin{equation}\label{eq2115}
F(\mu A,\mu p)=\mu F(A,p).
\end{equation}
In particular, $F(0,0)=0$, which we also know from Proposition 17.10.

If we take $\mu=1$, then \eqref{eq2114} becomes $F(A+\lambda (p\otimes p), p)= F(A,p)$. If $N=1$, this means that $F$ depends only on $p\in\RR$, and we conclude that
\begin{equation}\label{eq2117}
F(A,p)=
\begin{cases}
\kern0.55cm F(1)p\quad\text{if }p\geq0,\\
-F(-1)p\quad\text{if }p\leq0.
\end{cases}
\end{equation}
More interesting situation occur if $N\geq2$, as we have already seen in case $N=2$. From now on we assume that $N\geq2$.

We need to introduce some notation. For $p\in\RR^N$, $p\not=0$, consider the linear operator defined by the matrix $Q_p=I_N-(1/|p|^2)(p\otimes p)$. It is easy to verify that $Q_p$ is the projection of $\RR^N$ onto the hyperplane $p^\perp$ (also denoted by $(\RR p)^\perp$). Indeed, If $q=\lambda p$, then $Q_pq=0$; if $p\cdot q=0$, then $Q_pq=q$. Let $A$ be an $N\times N$ symmetric matrix and consider the matrix $Q_pAQ_p$. Since $Q_p$ is symmetric, it is clear that $Q_pAQ_p$ is also symmetric. It is also clear that $q\in(\RR p)^\perp$ implies that $Q_pAQ_pq\in(\RR p)^\perp$ and that $q\in\RR p$ implies that $Q_pAQ_pq=0$. Since $Q_pAQ_p$ is symmetric, it has $N$ real eigenvalues, one of which we have just seen to be zero. Let $\kappa_1,\kappa_2\ldots,\kappa_{N-1}$ denote the $N-1$ other eigenvalues. These are the eigenvalues of $Q_pAQ_p$ restricted to $(\RR p)^\perp$. If $A=D^2u$ and $p=Du$, and if we define $\lambda_i=\kappa_i/|p|$, $1\leq i\leq N-1$, then the
$\lambda_i$ are that principle curvatures of the level hypersurface of $u$ (Definition 4.19). If $N=2$, then by Definition 4.14, $\lambda_1=(1/|p|){\rm trace}(Q_pAQ_p)={\rm curv}(u)$.

\begin{theorem}[Giga, Goto \cite{}]Let $\{T_t\}$ be a contrast-invariant scale space and assume that $N\geq2$. Then the associated function $F$ satisfies the following relation: For all $A\in S^N$ and all $p\in\RR^N$, $p\not=0$,
\begin{equation}\label{eq2118}
F(A,p,t)=F(Q_pAQ_p,p,t).
\end{equation}
\end{theorem}

\begin{proof}We begin by fixing $p\in\RR^N$, $p\not=0$ and selecting an orthogonal coordinate system such that $p=|p|(0,\ldots,0,1)$. Then $p\otimes p=|p|^2(\delta_{Ni}\delta_{Nj})$, $1\leq i,j\leq N$. If we write $B=A+\lambda(p\otimes p)$, then $b_{ij}=a_{ij}+\lambda |p|^2(\delta_{Ni}\delta_{Nj})$. This means that $b_{ij}=a_{ij}$ except for $i=N$ and $j=N$, in which case $b_{NN}=a_{NN}+\lambda |p|^2$. Since $F(A+\lambda (p\otimes p), p)= F(A,p)$, this means that $F(A,p)$ does not depend on $a_{NN}$. We use this fact, combined with the assumption that $F$ is nondecreasing in its first variable, to complete the proof.

Note that, with the coordinate system we have chosen, $Q_pAQ_p$ is just the matrix $A$ with the last column and last row replaced with zeros: If $C=Q_pAQ_p$, then $c_{ij}=a_{ij}$ for $1\leq i,j\leq N-1$ and $c_{ij}=0$ if $i=N$ or if $j=N$. Now let $M=a_{N,1}^2+\cdots+a_{N,N-1}^2$ and consider $I_\varepsilon=\varepsilon I+(M/\varepsilon -\varepsilon)(\delta_{Ni}\delta_{Nj})$, $1\leq i,j\leq N$. Thus, $I_\varepsilon$ is an $N\times N$ diagonal matrix $D$, where $d_{ii}=\varepsilon$ for $1\leq i\leq N-1$ and $d_{NN}=M/\varepsilon$. One can easily verify that $Q_pAQ_p\leq A+I_\varepsilon$ and that $A\leq Q_pAQ_p+I_\varepsilon$ for small $\varepsilon>0$. Then we have
\[
F(A,p)\leq F(Q_pAQ_p+I_\varepsilon,p)\leq F(A+2I_\varepsilon,p).
\]
As we let $\varepsilon\to0$, the entries in the matrix $A+2I_\varepsilon$ tend to $a_{ij}$ except the entry $a_{NN}+2M/\varepsilon$, which tends to $+\infty$. But $F$ is independent of the value of $NN$-entry, and $F$ is continuous in its first variable. Thus,
\[
F(A+2I_\varepsilon,p)\to F(A,p)\quad\text{and}\quad F(Q_pAQ_p+I_\varepsilon,p)\to F(Q_pAQ_p,p).\qedhere
\]
\end{proof}

\begin{corollary}Let $\{T_t\}$ be a contrast-invariant scale space and assume that $N\geq2$. If $\{T_t\}$ is also isometric, then
\begin{equation}\label{eq2119}
F(A,p,t)=|p|G(\lambda_1,\ldots,\lambda_{N-1},t)
\end{equation}
for all $A\in S^N$, $p\in\RR$, $p\not=0$, where $G$ is a continuous function on
$\RR^{N-1}$ that is symmetric in the $N-1$ variables $\lambda_1,\ldots,\lambda_{N-1}$ and is nondecreasing with respect to each $\lambda_i$, $1\leq i\leq N-1$.
\end{corollary}


\begin{proof}By Lemma 17.15, the function $F$ associated with the scale space satisfies
\begin{equation}\label{eq2120}
F(RAR',Rp)=F(A,p)
\end{equation}
for all $A\in S^N$, $p\in\RR^N$, $p\not=0$, and $R\in O_N$. (Recall that $O_N$ denotes the group of linear isometries of $\RR^N$ (section 17.4.1).)

Fix $p\not=0$ and let $R$ be any element of the subgroup $O_N^p$ of $O_N$ that leaves $p$ fixed, that is, $Rp=p$. Since $Q_pAQ_p\in S^N$, we know from \eqref{eq2120} that
\[
F(RQ_pAQ_pR',Rp)=F(RQ_pAQ_pR',p)=F(Q_pAQ_p,p).
\]
By Theorem 18.5, $F(Q_pAQ_p,p)=F(A,p)$. These two relations tell us that
\[
F(RQ_pAQ_pR',p)=F(A,p)
\]
for all $R\in O_N^p$. This means that the value of $F(A,p)$ depends only on $p$ and the eigenvalues of $Q_pAQ_p$. Indeed, using the same coordinate system used in the proof of Theorem 18.5 based on $p=|p|(0,\ldots,1)$, there is always an $R\in O_N^p$ so that $RQ_pAQ_pR'$ is diagonal with entries $\kappa_1,\kappa_2,\ldots,\kappa_{N-1},0$, where the $\kappa_i$ are the eigenvalues of $Q_pAQ_p$ restricted to $(\RR p)^\perp$. Furthermore, we can choose $R$ so that the $\kappa_i$ appear in any order. Thus, there is a function $G_1$ such that
\[
F(A,p)=G_1(\kappa_1,\kappa_2,\ldots,\kappa_{N-1},p);
\]
$G_1$ is continuous and symmetric in the $\kappa_i$, and $G_1$ is nondecreasing in each $\kappa_i$. (These last statements follow from the fact that $F$ is continuous and nondecreasing in its first variable.)

Now take $R\in O_N$ and let $q=Rp$ ($p$ is still fixed). Then $|p|=|q|$. Furthermore, given any $q\in\RR^N$ such that $|p|=|q|$, there is an $R\in O_N$ such that $Rp=q$. It is easy to verify that $R(p\otimes p)=q\otimes p$, and since $(q\otimes p)'=p\otimes q$, that $(p\otimes p)R'=p\otimes q$. Thus, $R(p\otimes p)R'=q\otimes q$, which implies that $RQ_p=Q_qR$. Consequently,
\[
Q_qRAR'Q_q=RQ_pAQ_pR',
\]
and this means that $Q_qRAR'Q_q$ and $Q_pAQ_p$ have the same eigenvalues. Using \eqref{eq2120} again, we see that
$
F(RQ_pAQ_pR', Rp)=F(Q_pAQ_p,p),
$
and since $Rp=q$,
\[
F(RQ_pAQ_pR', q)=F(Q_pAQ_p,p).
\]
Since $Q_qRAR'Q_q$ and $Q_pAQ_p$ have the same eigenvalues, this implies that
\[
F(A,p)=G_1(\kappa_1,\kappa_2,\ldots,\kappa_{N-1},p)=G_1(\kappa_1,\kappa_2,\ldots,\kappa_{N-1},q)
\]
whenever $|p|=|q|$. This means that $F$ depends only on the modulus of $p$, and therefor we can write $F(A,p)=G_1(\kappa_1,\kappa_2,\ldots,\kappa_{N-1},|p|)$. Since $F$ is homogeneous,
\[
G_1(\mu\kappa_1,\mu\kappa_2,\ldots,\mu\kappa_{N-1},\mu|p|)=\mu G_1(\kappa_1,\kappa_2,\ldots,\kappa_{N-1},|p|)
\]
for $\mu\geq0$. If we take $\mu=|p|^{-1}$, then
\[
F(A,p)=|p|G_1(\kappa_1/|p|,\kappa_2/|p|,\ldots,\kappa_{N-1}/|p|,1).
\]
Defining $G$ by $G(\lambda_1,\lambda_2,\ldots,\lambda_{N-1})=G_1(\kappa_1/|p|,\kappa_2/|p|,\ldots,\kappa_{N-1}/|p|,1)$, where the $\lambda_i= \kappa_i/|p|$, completes the proof.
\end{proof}

\section[Affine-invariant scale spaces for ${N\geq2}$]{Affine-invariant scale spaces for $\bm{N\geq2}$}

There is a function $H_N$ in the following theorem that is defined on the set of $N$ integers $\{-N+1+2k\mid 0\leq k\leq N-1\}$. We will see in the proof of the theorem that $H_N$ is nondecreasing and that it vanishes except at the points $-(N-1)$ and $N-1$. It will also be shown that $H_N(N-1)\geq0$. There is not enough information to determine the value of $H_N(N-1)$; however, to avoid the trivial case $F\equiv0$, we assume that $H_N(N-1)>0$.

\begin{theorem}Assume that the scale space $\{T_t\}$ is contrast invariant and affine invariant. Assume also that $T_t(-u)=-T_t(u)$ and that $\{T_t\}$ has been normalized in accordance with Lemma 17.20. Then the PDE associated with $\{T_t\}$ is
\begin{equation}\label{eq2121}
\frac{\partial u}{\partial t}=|Du|t^{\frac{N-1}{N+1}}\prod_{i=1}^{N-1}|\lambda_i|^{\frac{1}{N+1}}H_N\Big(\sum_{i=1}^{N-1}{\rm sgn}(\lambda_i)\Big),
\end{equation}
where the $\lambda_i$ are the principal curvatures of the level hypersurface of $u$,  ${\rm sgn}(\lambda_i)$ denotes the sign of $\lambda_i$, and $H_N$ is such that
$H_N(N-1)>0$, $H_N(N-1)=-H_N(-(N-1))$, and $H(n)=0$ for all $-(N-1)<n<N-1$. In other words, $H_N$ is equal to zero if all the $\lambda_i$ do not have the same sign.
\end{theorem}

\begin{proof}We begin with the result of Corollary 18.6: Since $\{T_t\}$ is contrast invariant and isometric, its associated function $F$ is of the form
\[
F(A,p,t)=|p|G(\lambda_1,\lambda_2,\ldots,\lambda_{N-1},t),
\]
and $G$ is symmetric with respect to the $\lambda_i$. If $p\not=0$, then $\lambda_i=\kappa_i/|p|$, where the $\kappa_i$, $1\leq i\leq N-1$ are the eigenvalues of $A$ restricted to the hyperplane $p^\perp$ orthogonal to $p$. To simplify the proof, we prefer to use the more general form of $F$ that appeared in the proof of Corollary 18.6, namely,
\begin{equation}\label{eq2122}
F(A,p,t)=G_1(\kappa_1,\kappa_2,\ldots,\kappa_{N-1},|p|,t).
\end{equation}

Since the restriction of $A$ to the hyperplane $p^\perp$ is represented by a symmetric matrix, we can choose orthonormal vectors $e_1,\ldots,e_{N-1}$ such that $\kappa_i=A(e_i,e_i)$, $1\leq i\leq N-1$. Each vector $e_i$ is orthogonal to $p$, so we obtain an orthonormal basis for $\RR^N$ by including the vector $e_N=p/|p|$. We now define some special linear affine transformations of $\RR^N$: Let $B_i$, for $1\leq i\leq N-1$, be the linear transform defined by
\[
B_i(e_1,\ldots,e_i,\ldots,e_N)=(e_1,\ldots,\beta e_i,\ldots,\beta^{-1}e_N),
\]
where $\beta\in\RR$, $\beta\not=0$. Clearly, $|B_i|=1$. We are now going to apply the result of Lemma 17.21 with $B=B_1$. This says that $F(A,p,t)=F(B_1AB_1',B_1p,t)$, and in view of the representation \eqref{eq2122}, this means that
\[
F(A,p,t)=G_1(\beta^2\kappa_1,\kappa_2,\ldots,\kappa_{N-1},\beta^{-1}|p|,t).
\]
Assume for the moment that $\kappa_1\not=0$ and take $\beta=|\kappa_1|^{-1/2}$. Then
\[
F(A,p,t)=G_1({\rm sgn}(\kappa_1),\kappa_2,\ldots,\kappa_{N-1},|\kappa_1|^{1/2}|p|,t).
\]
Repeat this argument with $B=B_i$ for $i=2$ to $i=N-1$. The result is that
\begin{equation}\label{eq2123}
F(A,p,t)=G_1\Big({\rm sgn}(\kappa_1),\ldots,{\rm sgn}(\kappa_{N-1}),|p|\prod_{i=1}^{N-1}|\kappa_i|^{1/2},t\Big),
\end{equation}
assuming that $\kappa_i\not=0$, $1\leq i\leq N-1$. We return again to Lemma 17.21, which is based on the results of Lemma 17.20, and note that
\[
F(\mu^2A,\mu p,t)=\mu F(A,p,\mu t)
\]
for $\mu\geq0$ implies that
\begin{equation*}
\begin{split}
G_1\Big({\rm sgn}(\kappa_1),\ldots,{\rm sgn}(\kappa_{N-1}),&\mu|p|\mu^{N-1}\prod_{i=1}^{N-1}|\kappa_i|^{1/2},t\Big)\\
&=\mu G_1\Big({\rm sgn}(\kappa_1),\ldots,{\rm sgn}(\kappa_{N-1}),|p|\prod_{i=1}^{N-1}|\kappa_i|^{1/2},\mu t\Big).
\end{split}
\end{equation*}
We deduce that
\begin{equation*}
\begin{split}
\mu^{-1}G_1\Big({\rm sgn}(\kappa_1),\ldots,{\rm sgn}(\kappa_{N-1}),&\mu^N|p|\prod_{i=1}^{N-1}|\kappa_i|^{1/2},\mu^{-1}t\Big)\\
&=G_1\Big({\rm sgn}(\kappa_1),\ldots,{\rm sgn}(\kappa_{N-1}),|p|\prod_{i=1}^{N-1}|\kappa_i|^{1/2},t\Big).
\end{split}
\end{equation*}
By taking $\mu=t$, we see that
\[
F(A,p,t)=t^{-1}G_1\Big({\rm sgn}(\kappa_1),\ldots,{\rm sgn}(\kappa_{N-1}),t^N|p|\prod_{i=1}^{N-1}|\kappa_i|^{1/2},1\Big),
\]
and we write
\[
F(A,p,t)=t^{-1}G_2\Big(t^N|p|\prod_{i=1}^{N-1}|\kappa_i|^{1/2},{\rm sgn}(\kappa_1),\ldots,{\rm sgn}(\kappa_{N-1})\Big).
\]
At this point we use the fact that $\{T_t\}$ is contrast invariant, and so we have
\[
F(\alpha^{-1}A,\alpha^{-1}p,t)=\alpha^{-1}F(A,p,t)
\]
for all $\alpha>0$. Thus,
\[
tF(A,p,t)=\alpha G_2\Big(\alpha^{-1}t^N|p|\prod_{i=1}^{N-1}|\alpha^{-1}\kappa_i|^{1/2},{\rm sgn}(\kappa_1),\ldots,{\rm sgn}(\kappa_{N-1})\Big).
\]
By taking $\alpha=(t^N|p|\prod_{i=1}^{N-1}|\kappa_i|^{1/2})^{2/(N-1)}$, the function $F$ is reduced to the following form:
\begin{align*}
F(A,p,t)&=t^{\frac{N-1}{N+1}}|p|^{\frac{2}{N+1}}\prod_{i=1}^{N-1}|\kappa_i|^{\frac{1}{N+1}}G_2(1,{\rm sgn}(\kappa_1),\ldots,{\rm sgn}(\kappa_{N-1})\\
&=t^{\frac{N-1}{N+1}}|p|^{\frac{2}{N+1}}\prod_{i=1}^{N-1}|\kappa_i|^{\frac{1}{N+1}}H_1({\rm sgn}(\kappa_1),\ldots,{\rm sgn}(\kappa_{N-1}).
\end{align*}
Since $\lambda_i=\kappa_i/|p|$, we finally have
\begin{equation}\label{eq2123a}
F(A,p,t)=|p|t^{\frac{N-1}{N+1}}\prod_{i=1}^{N-1}|\lambda_i|^{\frac{1}{N+1}}\,H_1({\rm sgn}(\lambda_1),\ldots,{\rm sgn}(\lambda_{N-1}).
\end{equation}
The derivation of this representation of $F$ was based on the assumption that none of the eigenvalues $\kappa_i$ were zero. If there were $\kappa_i=0$, we could have perturbed $A$ by replacing these eigenvalues with $\varepsilon>0$, done the derivation with positive eigenvalues, and then let $\varepsilon$ tend to zero in \eqref{eq2123a}.

We must now deal with the function $H_1$, or more precisely, the functions $H_1$, for there is a different function for each value of $N\geq2$. First note that $H_1$ must be symmetric in its $N-1$ variables: $F$ is invariant under any rotation that leaves $p$ fixed, and we can always find an element of $O_N^p$ that produces any given permutation of the $\kappa_i$, and thus of the $\lambda_i$. If some $\lambda_i$ happens to be zero, we can set $H_1({\rm sgn}(\lambda_1),\ldots,{\rm sgn}(\lambda_{N-1}))=0$. Another way to do this is to define ${\rm sgn}(0)=0$ and say that $H_1({\rm sgn}(\lambda_1),\ldots,{\rm sgn}(\lambda_{N-1}))=0$ if any of its $N-1$ variables is zero. Thus the only interesting situation is in case all of the $\lambda_i$ are nonzero. Then by the invariance of $H_1$ under elements of $O_N^p$, it is clear that $H_1$ depends only on the number variables equal to one and the number of variables equal to minus one. In other words, $H_1$ is function of $\sum_{i=1}^{N-1}{\rm sgn}(\lambda_i)$:
\[
H_1({\rm sgn}(\lambda_1),\ldots,{\rm sgn}(\lambda_{N-1}))=H_N\Big(\sum_{i=1}^{N-1}{\rm sgn}(\lambda_i)\Big),
\]
where we have written $H_N$ to stress the fact that the functions depend on the dimension $N$. $H_N$ is defined on the $N$ integers $\{-N+1+2k\mid 0\leq k\leq N-1\}$, but we no information about its range. We do, however, have one last invariant to call on, and that is the assumption that $T_i(u)=-T_i(-u)$. This translates into the relation $F(-A,-p,t)=-F(A,p,t)$, which in turn implies that $H_N(n)=-H_N(-n)$. Finally, we know that $H_N$ must be nondecreasing based on the fact that $F$ is nondecreasing in its first variable, $A$. In summary,
\begin{equation}\label{eq2124}
F(A,p,t)=|p|t^{\frac{N-1}{N+1}}\prod_{i=1}^{N-1}|\lambda_i|^{\frac{1}{N+1}}\,H_N\Big(\sum_{i=1}^{N-1}{\rm sgn}(\lambda_i)\Big),
\end{equation}
where $H_N$ is a nondecreasing function defined on the set $\{-N+1+2k\mid 0\leq k\leq N-1\}$ and $H_N(n)=-H_N(-n)$. We are now going to consider three cases.

\medskip

\noindent \textbf{The case} ${N{\bf=2}}$.

Here we have $N-1=1$, and \eqref{eq2124} reads
\[
F(A,p,t)=t^{1/3}|p||\lambda_1|^{1/3}\,H_2({\rm sgn}(\lambda_1)).
\]
The value of $H_2(1)$ is not determined, although it must be positive to avoid the trivial case $F\equiv0$ and to ensure that $H_2(-1)=-H_2(1)$ and that $H_2$ is nondecreasing. Thus, up to a positive (multiplicative) constant $F(A,p,t)=t^{1/3}|p|{\rm sgn}(\lambda_1)|\lambda_1|^{1/3}$, which we have been writing as $F(A,p,t)=t^{1/3}|p|(\lambda_1)^{1/3}$, with the convention that $r^{1/3}=(r/|r|)|r|^{1/3}$. This can also be written as
\[
F(A,p,t)=t^{1/3}|p|\Bigg(\frac1{|p|}A\Bigg(\frac{p^\perp}{|p|},\frac{p^\perp}{|p|}\Bigg)\Bigg)^{1/3}.
\]
If $A=D^2u$ and $p=Du$, then the associated scale space equation if
\[
\frac{\partial u}{\partial t}=t^{1/3}|Du|({\rm curv}(u))^{1/3}.
\]

\medskip

\noindent \textbf{The case ${N{\bf=3}}$}.

The PDE we obtain in this case is
\[
\frac{\partial u}{\partial t}=t^{1/2}|Du||\lambda_1\lambda_2|^{1/4}H_3({\rm sgn}(\lambda_1)+{\rm sgn}(\lambda_2)),
\]
where $\lambda_1$ and $\lambda_2$ are the principal curvatures of the level surface of $u$. Their product is the Gaussian curvature of the level surface of $u$, and to highlight this we write the equation as
\begin{equation}\label{eq2124a}
\frac{\partial u}{\partial t}=t^{1/2}|Du||G(u)|^{1/4}H_3({\rm sgn}(\lambda_1)+{\rm sgn}(\lambda_2)).
\end{equation}

Since ${\rm sgn}(\lambda_1)+{\rm sgn}(\lambda_2)$ takes only the values $-2,0,2$, and since $H_3(-2)=-H_3(-2)$, we are concerned with only two parameters: $H_3(2)=b$ and $H_3(0)=a$. We know that $H_3(-2)\leq H_3(0)\leq H_3(2)$, or $-b\leq a \leq b$. Hence, $b\geq0$ and $|a|\leq b$. We are now going to show that $a=0$ by using the fact that $F$ is increasing with respect to its first variable. We do this by choosing special values for the pair $(\lambda_1$,$\lambda_2)$. For example, take $(-1,\alpha)$ and $(\alpha,\alpha)$, $\alpha>0$. The value of $F$ for the first pair is less than or equal to the value of $F$ for the second:
\[
\alpha H_3(0)\leq \alpha^2 H_3(2).
\]
Letting $\alpha$ tend to zero shows that $H_3(0)\leq0$. Making a similar argument with the pairs $(-\alpha,\alpha)$ and  $(\alpha,\alpha)$, shows that $H_3(0)\geq0$. Thus $H_3(0)=0$, which means that the left-hand side of \eqref{eq2124a} is zero if the two principal curvatures have opposite signs. Consequently, up to a positive multiplicative constant, equation \eqref{eq2124a} is
\begin{equation}\label{eq2125}
\frac{\partial u}{\partial t}={\rm sgn}(\lambda_1)t^{1/2}|Du||G(u)^+|^{1/4},
\end{equation}
where $x^+$ stands for $\sup\{0,x\}$. This equation describes the unique multiscale analysis in three dimensions that is both affine invariant and contrast invariant and satisfies the condition $T_t(u)=-T_t(-u)$.

\medskip

\noindent \textbf{The case ${N{\bf>3}}$}.

The only remaining task is to prove that $H_N$ has the properties stated in the theorem. This is done by using arguments similar to those use for the three-dimensional case: By taking particular values for the $\lambda_i$ and by using the fact that $F$ is nondecreasing, one shows that $H_N(N-3)=0$. Then since $H_N$ is nondecreasing and since $H_N(n)=-H_N(-n)$, it follows that $H_N(n)=0$ except for $n=N-1$ and $n=-(N-1)$. The details are left as an exercise.
\end{proof}

\begin{exercise}Fill in the details for the last part of the proof. \finex
\end{exercise}


\section{Comments and references}

\paragraph*{Axiomatics.} In this chapter, we have followed an axiomatic presentation of scale spaces developed in \cite{Alvarez:1993:AFE}, which is a simplified version of the original given in \cite{Guichard:1994:AAM}. Other axioms for affine scale space have been proposed by Olver, Sapiro, and Tannenbaum \cite{Olver:1996:AIG,Olver:1997:IGE}.

\paragraph*{Curvature motion.}The first complete mathematical study on the motion of a surface by its mean curvature is the book by Brakke \cite{Brakke:1978:MSM}. The main question in this field is, How regular is a surface that has been smoothed by mean curvature? Huisken proved that a convex surface smoothed by mean curvature was transformed into a sphere before vanishing to a point \cite{Huisken:1984:FMC}. This result generalizes to higher dimensions a result by Gage about curve evolution \cite{Gage:1984:CSM}. The question of whether or not a surface smoothed by curvature motion ended in a sphere was first introduced by Firey for Gaussian curvature motion \cite{Firey:1974:SWS}. Osher and Sethian developed the first numerical codes for mean curvature motion, where topological changes of the surface could be dealt with efficiently \cite{Osher:1988:FPCb}. Yuille observed that the Koenderink--van Doorn dynamic shape algorithm could create singularities is a dumb-bell shaped surface \cite{Yuille:1988:CSD}: The ``handle'' part ultimately evolved into a thin filament that broke, creating singularities. (See the figures in Chapter 2, particularly Figure 2.9.) This behavior contradicts causality, one of the main axioms of scales space: Smoothing a shape should not create new features. Koenderink comments on this creation of singularities in \cite{Koenderink:1989:HUS}. The corresponding mathematical study of this phenomenon is due to Grayson \cite{Grayson:1989:SNE}. Bounds on the gradient for the mean curvature equation are given by Barles in \cite{Barles:1991:IGB}. A general survey of singularity formation by mean curvature motion is given by Angenent in \cite{Angenent:1992:SRR}. Altschuler, Angenent, and Giga prove the smoothness of the evolution of rotationally symmetric hypersurfaces and estimate the number of singular points \cite{Altschuler:1995:MCF}. More about regularity and singularities related to mean curvature flow can be found in \cite{Evans:1987:RFN,Angenent:1997:DNM,Huisken:1997:SMC,Ilmanen:1998:ESG}. Ishii and Souganidis developed a theory of viscosity solutions for general curvature equations, including any power function of the curvature or the Gaussian curvature \cite{Ishii:1995:GMN}. Particular mention must be made about the work by Caselles and Sbert on the properties of scale spaces in three dimensions \cite{Caselles:1996:WBC}. They prove that the dumb-bell is not ``pinched off'' by the affine scale space, but they exhibit examples of other surfaces where singularities may appear. Chow proved that the affine scale space deforms strictly convex surfaces into spheres \cite{Chow:1985:DCH,Chow:1987:DCH}. This result is equivalent to the result by Huisken for mean curvature motion mentioned above.

\paragraph*{Extensions of affine scale space in two dimensions.} Several authors have attempted to extend the affine scale space in two dimensions to a projective-invariant scale space. The results of this chapter have clearly shown that a multiscale analysis that is both local and causal cannot be projective invariant. An affine-invariant scale space must have the form given in equation \eqref{eq2121}, which is completely determined up to a multiplicative constant. Thus, by requiring affine invariance, we have exhausted all degrees of freedom in the choice of the PDE. The way around this is to relax one or more of the other requirements, but not one of the invariants in the projective group. Faugeras and Keriven \cite{Faugeras:1995:ACA,Faugeras:1995:SSA,Faugeras:1995:SRR,Faugeras:1994:CMF} and Bruckstein and Shaked \cite{Bruckstein:1997:PIS} give up the maximum principle. They then derive higher order PDEs that can hardly be considered smoothing operators. Establishing existence proofs and numerical simulations of this projective curve scale space are open problems. (See also Olver, Sapiro, and Tannenbaum \cite{Olver:1994:CUI}.) Dibos does not give up locality or causality, and she is able to simulate her scale space numerically. This scale space no longer depends on a single scale parameter, but rather on two parameters. Geraets and others propose affine-invariant scale spaces for discrete sets with applications to object recognition \cite{Geraets:1995:ASS,Geraets:1995:ORA}. One of the first attempts to use the AMSS model for affine-invariant shape recognition was given by Cohignac, Lopez and Morel \cite{Cohignac:1994:ILA}. A more complete and sophisticated attempt, which performs image comparison by applying the affine scale space to all level lines of each image, is found in \cite{Lisani:2000:AIM}. Alvarez and Morales used the affine scale space for corner and T-junction detection in digital images \cite{Alvarez:1997:AMM}.
