%gmChap05.tex. 

\graphicspath{{./figures/chapter5/}}

\chapter{The Main Contrast-Invariant Equations}

The purpose of this chapter is to introduce those contrast-invariant PDEs that are essential for contrast-invariant image analysis. These are the differential equations that will appear later in asymptotic results similar to the results in Theorem 2.3. There, we related the heat equation to a linear integral operator. In the later results, the PDEs presented in this chapter will replace the heat equation, and nonlinear contrast-invariant operators will replace the linear integral operator. The differential geometry used in this chapter was developed in Chapter 4, and in that sense this chapter follows Chapter 4 directly. In fact, Chapters 4 and 5 form a logical unit. 

\section{The definition of a shape and how it is recognized}

Recall that a \textit{shape} was defined by Koendernik and van Doorn as a closed subset of $\RR^N$ (section 2.4); recall further the problems that arose when such shapes were smoothed using the Gaussian (Figures 2.9 and 2.10). This highlights the fact that there are two interacting ideas here: the definition of shape and the means of smoothing. In our approach,  smoothing is more fundamental, and thus we need to define shape so it is compatible with our concepts of contrast-invariant smoothing and shape recognition. We wish to reduce image smoothing to smoothing the level sets of an image and, further, to smoothing the boundaries of these level sets. Thus, based on what we have done in Chapter 4, it would be natural to define a shape as a compact set in $\RR^2$ whose boundary is a finite set of Jordan curves. If all of these Jordan curves are disjoint, we have an unambiguous picture, but if the curves touch or coincide in places, problems, both theoretical and practical, arise. These are important problems, but they are outside the main focus of the book. For these reason, we are going to make the following very restrictive definition of shape. 

\begin{definition} An elementary shape is a compact set in $\RR^2$ whose interior is the interior of a rectifiable Jordan curve.
\end{definition} 

The implication of this definition is that real shapes are made up of these elementary shape, but by considering only these elementary shapes we avoid the problems hinted at above. Thus, is what follows, we will be smoothing and recognizing individual Jordan curves.

In images of a natural environment, most observed objects are partially hidden (occluded) by other objects and often deformed by perspective. When we observe a Jordan curve we cannot be sure that it belongs to a single object; it may be composed of pieces of the boundaries of several objects that are occluding each other. Shape recognition technology has therefore focused on local methods, that is, methods that work even if a shape is not in full view and if the visible part is distorted. As a consequence, image analysis adopts the following principle: \textit{Shape recognition must be based on local features of the shape's boundary, in this case, local features of the Jordan curve and not on its global features. If the boundary has some degree of smoothness, then these local features are based on the derivatives of the curve, which can include the tangent vector, curvature, and so on.} 

Before beginning the technical aspects of our version of shape recognition, we note that most local recognition methods involve the ``salient'' points of a shape, which are the points where the curvature is zero (inflection points) and points where the curvature has a maximum or minimum (the ``corners'' of the shape). These methods reduce a shape to a finite code that consists of the coordinates of a set of characteristic points, which are mainly corners and inflection points. Recognition then amounts to comparing these sets of numbers. This is done statistically.

\section{Multiscale features and scale space}

The methods we have just outlined---in fact, all nonglobal computational shape recognition methods---make the following two basic assumptions, neither of which is true in practice for the analyzed shapes:
\begin{enumerate}[$\bullet$]\setlength\itemsep{2pt}
\item The shape has a smooth boundary (a smooth Jordan curve).
\item The boundary has a finite number of inflexion points and points where the curvature has a local maximum or local minimum.
\end{enumerate}

The fact that these conditions can be obtained by properly smoothing a Jordan curve was proven in 1986 by Gage and Hamilton \cite{Gage:1986:HESa} and in 1987 by Grayson \cite{Grayson:1987:HESb}. They showed that it is possible to transform a rectifiable Jordan curve into a smooth Jordan curve by using the so-called \textit{intrinsic heat equation}. 

Before proceeding, we wish to inject a comment about notation. For convenience, and unless it would cause ambiguity, we will not make a distinction between a Jordan curve $\Gamma$ (the topological object) and a function $x\mapsto\fxx(x)$ such that $\Gamma=\{\fxx(x)\}$. As we have already done, we will speak of the Jordan curve $\fxx$. Since we will be speaking of families of Jordan curves dependent on a parameter $t>0$, we will most often denote these families by $\fxx(t,y)$, where the second variable is the parameterization of the Jordan curve. Thus, $\fxx(t,y)$ has three meanings: a family of Jordan curves, a family of functions that represent these curves, and a particular point on one of these curves. We will usually use $s$ to denote an arc-length parameter. Finally, everything we do in this chapter is local---it takes place in some neighborhood of a given point. This means we are generally speaking of Jordan arcs.

\begin{definition}Let $\fxx(t,s)$, $t>0$, be a family of $C^2$ Jordan curves and assume that for each $t$, $s$ is an arc length parameterization of $\fxx(t,s)$. We say that $\fxx(t,s)$ satisfies the intrinsic heat equation if
\begin {equation}\label{eq61x}
\frac{\partial\fxx}{\partial t}(t,s)=\frac{\partial^2\fxx}{\partial s^2}(t,s)={\rm Curv}(\fxx)(t,s).
\end{equation}
\end{definition}

\begin{theorem}[Grayson]Let $\fxx_0$ be a Jordan curve with finite length. By using the intrinsic heat equation, it is possible to evolve $\fxx_0$ into a family of Jordan curves $\fxx(t,s)$ such that $\fxx(0,s)=\fxx_0(s)$ and such that for every $t>0$, $\fxx(t,s)$ is $C^\infty$ and satisfies equation \eqref{eq61x}. Furthermore, $\fxx(t,s)$ has only a finite number of inflection points and curvature extrema, and the number of these points does not increase with $t$. For every initial curve, there is a scale $t_0$ such that the curve $\fxx(t,s)$ is convex for $t\geq t_0$ and there is a scale $t_1$ such that the curve $\fxx(t,s)$ is a single point for $t\geq t_1$.
\end{theorem}

We have assumed that the initial curve $\fxx_0$ has finite length. This means that $\fxx_0$ is rectifiable and, consequently, is differentiable almost everywhere. That is about all one can say about $\fxx_0$. However, the finite-length assumption is enough to ensure that, for each $t>0$, $\fxx(t,s)$ is $C^\infty$ and the scalar function $\fxn(t,s)\cdot{\rm Curv}(\fxx)(t,s)$ has finitely many zero-crossings and extrema. (Here we have defined the normal vector $\fxn$ as the tangent vector $\partial\fxx/\partial s$ rotated to the left by $\pi/2$.) What is even better is that the number of these characteristic points can only decrease as the ``time parameter'' $t$ increase. This means that the scale space is causal in the terminology of vision theory. (Recall that in Chapter 2 we said that a process is causal if it did not introduce new features.) These results of Gage and Hamilton and of Grayson were quickly embraced by the image processing community, where several attempts to define \textit{scale space} for shapes had already come very close to the equation studied by these investigators.

It is time to say what we mean by ``scale space.'' We will refer to any process that smooths a shape (which is represented here by a Jordan curve) and that depends on a real parameter $t$ (which measures the degree of smoothing) a \textit{shape scale space}. Thus a shape scale space associates with an initial Jordan curve $\fxx(0,s)=\fxx_0(s)$ a family of smooth curves $\fxx(t,s)$. For example, the intrinsic heat equation eliminates spurious details of the initial shape and retains simpler, more reliable versions of the shape, and these smoothed shapes have finite codes. Suppose that we wish to compare two original versions of a shape $\fxx_0$ and $\fxx_1$ that have been captured under different conditions of noise and distortions. Comparing these two shapes is simply impossible. If, however, they are smoothed to the shapes $\fxx_0(t,\cdot)$ and $\fxx_1(t,\cdot)$, then it is possible to compare the codes of $\fxx_0(t,\cdot)$ and $\fxx_1(t,\cdot)$.

\section{From image motion to curve motion}

The intrinsic heat equation is only one example from a large family of nonlinear equations that move curves with a curvature-dependent speed, that is, $\partial\fxx/\partial t$ is a function of the curvature of the curve $\fxx$. The only requirement for our purposes is that the speed is a nondecreasing function of the magnitude of the curvature $|{\rm Curv}(\fxx)|$.

\begin{definition}We say that a $C^2$ function $u:\RR^+\times\RR^2\to\RR$ satisfies a curvature equation if for some real-valued function $g(\kappa, t)$, which is nondecreasing in $\kappa$,
\begin{equation}\label{eq65x}
\frac{\partial u}{\partial t}(t,\fxx)=g({\rm curv}(u)(t,\fxx), t)|Du|(t,\fxx).
\end{equation}
\end{definition}

\begin{definition}Let $\fxx(t,s)$ be a family of $C^2$ Jordan curves such that for every $t>0$, $s\mapsto\fxx(t,s)$ is an arc-length parameterization. We say that the functions $\fxx(t,s)$ satisfy a curvature equation if for some real-valued function $g(\kappa, t)$, which is nondecreasing in $\kappa$, they satisfy
\begin{equation}\label{eq64x}
\frac{\partial\fxx}{\partial t}(t,s)= g(|{\rm Curv}(\fxx)(t,s)|,t)\fxn(t,s),
\end{equation}
where $\fxn$ is a unit vector in the direction of ${\rm Curv}(\fxx)$.
\end{definition}

The fact that this last equation does not make sense if ${\rm Curv}(\fxx)=0$ is not a problem, since it is easily fixed in the cases we consider. We will only be interested in $g$ that are symmetric in their first variable: $g(-\kappa,t)=-g(\kappa,t)$ for all $t>0$. With this assumption, we proceed as follows: The Jordan curves $\fxx(t,s)$ all have $C^1$ unit tangents ${\bm{\tau}}=\partial\fxx/\partial s=\fxx'$, and hence $C^1$ normals $\fxn={\bm{\tau}}^\perp$. In the notation of Proposition 4.4, ${\rm Curv}(\fxx)={\bm{\kappa}}={\bm{\tau}}'$. The vectors $\fxn$ and ${\bm{\kappa}}$ are collinear so we can write ${\bm{\kappa}}=\kappa\fxn$, where $\kappa={\bm{\kappa}}\cdot\fxn$. Then \eqref{eq64x} becomes
\begin{equation}\label{eq64z}
\frac{\partial\fxx}{\partial t}(t,s)=g(\kappa(t,s),t)\fxn(t,s).
\end{equation}

All of these equations are candidates to be curve or image scale spaces, and one of the main objectives of this book is to identify precisely those equations that are relevant for image analysis. The above definitions are quite restrictive because they require the curves or image to be $C^2$. A more generally applicable definition of solutions for these equations will be given in Chapter 15 with the introduction of viscosity solutions. Our immediate objective is to establish the link between the motion of an image and the motion of its level lines. This will establish the relation between equations \eqref{eq65x} and \eqref{eq64x}.

\subsection{Curvature equations for curves and real-valued functions}

\begin{lemma}Suppose that $(t,\fxx)\mapsto u(t,\fxx)$ is $C^2$ in a neighborhood $T\times U$ of the point $(t_0,\fxx_0)\in\RR\times\RR^2$, and assume that $Du(t_0,\fxx_0)\not=0$. Then there exists an open interval $J$ centered at $t_0$, an open disk $V$ centered at $\fxx_0$, and a unique $C^1$ function $\fxx:J\times V\to\RR^2$ that satisfy the following properties:
\begin{enumerate}[$(i)$]\setlength\itemsep{2pt} 
\item $u(t,\fxx(t,\fxy))=u(t_0,\fxy)$ and $\fxx(t_0,\fxy)=\fxy$ for all $(t,\fxy)\in J\times V$.
\item The vectors $(\partial\fxx/\partial t)(t,\fxy)$ and $Du(t,\fxx(t,\fxy))$ are collinear.
\item The function $\fxx$ satisfies the following differential equation:
\begin{equation}\label{eq66x}
\frac{\partial\fxx}{\partial t}(t,\fxy)=-\Big(\frac1{|Du|}\frac{\partial u}{\partial t}\Big)\frac{Du}{|Du|}(t,\fxx(t,\fxy)).
\end{equation}
\end{enumerate} 
\end{lemma}

\begin{proof}We begin be assuming that a $C^1$ function $\fxx$ exists and satisfies $(i)$. By differentiating the expression $u(t,\fxx(t,\fxy))=u(t_0,\fxy)$ with respect to $t$, we see that 
\[
\frac{\partial u}{\partial t}(t,\fxx(t,\fxy))+Du(t,\fxx(t,\fxy)\cdot\frac{\partial\fxx}{\partial t}(t,\fxy)=0.
\]
The vectors $(\partial\fxx/\partial t)(t,\fxy)$ and $Du(t,\fxx(t,\fxy))$ are collinear if and only if $\fxx$ satisfies equation \eqref{eq66x}. Our proof focuses on the solutions of equation \eqref{eq66x}, and to make things more transparent, we write equation \eqref{eq66x} as follows:
\begin{equation}\label{eq66a}
\frac{\rmd\fxx}{\rmd t}(t)={\bm f}(t,\fxx(t)),
\end{equation}
where 
\[
{\bm f}(t,\fxx(t))=-\Big(\frac1{|Du|}\frac{\partial u}{\partial t}\Big)\frac{Du}{|Du|}(t,\fxx(t)).
\]
We have suppressed the parameter $\fxy$, which will be the initial value of the solution of equation \eqref{eq66a}, to clarify the properties of ${\bm f}$ and the properties of the solutions of \eqref{eq66a}. 

Since $u$ is $C^2$ in $T\times U$, ${\bm f}$ is continuously differentiable at any point $(t,\fxy)\in T\times U$ where $Du(t,\fxy)\not={0}$. The assumption that $Du(t_0,\fxx_0)\not={0}$ implies that this is true in a neighborhood of $(t_0,\fxx_0)$, which, to avoid more notation, we assume is $T\times U$. Thus, ${\bm f}$ is continuously differentiable on $T\times U$, and consequently ${\bm f}$ satisfies a Lipschitz condition at each point of 
$T\times U$. We can now apply a version of Cauchy--Lipschitz theorem that includes dependence of the solutions on initial conditions: 
\begin{enumerate}[$(1)$]\setlength\itemsep{2pt}
\item There is an open interval $J\subset T$ centered at $t_0$ and an open disk $V\subset U$ centered at $\fxx_0$ such that, for every point $(t',\fxy)\in J\times V$, there is a unique solution $t\mapsto\fxx(t,t',\fxy)$ of equation \eqref{eq66a}, whose values are in $U$ and such that $\fxx(t',t',\fxy)=\fxy$.
\item The mapping $(t,t',\fxy)\mapsto\fxx(t,t',\fxy)$ is uniformally continuous on $J\times J\times V$.
\item There is an open disk $W\subset V$ centered at $\fxx_0$ such that, for any point $(t,t',\fxy)$ in $J\times J\times W$, the equation $\fxy=\fxx(t',t,\fxz)$ has the unique solution $\fxz=\fxx(t,t',\fxy)$ in $V$. 
\end{enumerate}
This is clearly more than we need to prove the lemma. We will complete the proof of the lemma and then comment on other properties of the solutions.

The proof is essentially complete; we need only to interpret (1). For the lemma, we take the $J$ and $V$ of item (1). The function $t\mapsto\fxx(t,t',\fxy)$ is the unique solution of equation \eqref{eq66x}, and by taking $t'=t_0$ in (1) we have the boundary condition that appears in $(i)$. Condition $(ii)$ is clearly satisfied because $\fxx$ satisfies \eqref{eq66x}. Finally, the solution $(t,t_0,\fxy)\mapsto\fxx(t,t_0,\fxy)$, which we write $\fxx(t,\fxy)$, satisfies $u(t,\fxx(t,\fxy))=u(t_0,\fxy)$: The derivative with respect to $t$ is zero, so $u(t,\fxx(t,\fxy))$ is a constant, and we know that $u(t_0, \fxx(t_0,\fxy))=u(t_0,\fxy)$. 
\end{proof}

We wish to relate this result directly to the movement of the level lines of $u$. Thus, let $\Gamma(t_0,\fxx_0)$ denote the level line $\{\fxy\mid u(t_0,\fxy)=u(t_0,\fxx_0)\}$ and parameterize $\Gamma(t_0,\fxx_0)$ by an arc length  $s\in(-\varepsilon,\varepsilon)$ such that $\fxy(0)=\fxx_0$. For a fixed $t\in J$, consider the function $s\mapsto\fxx(t,t_0,\fxy(s))$. This is a continuous function of $s$ (by (2)), and it is one-to-one for $\fxy(s)\in W$ (by (3)). Furthermore, $u(t, \fxx(t,\fxy(s))=u(t,\fxy(s))=u(t_0,\fxx_0)$ by $(i)$ and the fact that $\fxy(s)\in\Gamma(t_0,\fxx_0)$. This means that $s\mapsto\fxx(t,t_0,\fxy(s))$ is a Jordan arc that agrees with the level line of $u$ that passes through $\fxx(t, \fxy(0))$, which means, by the uniqueness of this level line, that $s\mapsto\fxx(t,t_0,\fxy(s))$ is the level line of $u$ at level $u(t_0,x_0)$ is some neighborhood of $\fxx(t, \fxy(0))$. The point of this is that the solutions of equation \eqref{eq66x} describes more than the motion of points $\fxy$: If the initial values $\fxy$ are restricted to the level curve $\Gamma(t_0,\fxx_0)$, then the equation describes the evolution of this curve, and the evolved curves are again level curves of $u$ at the same level as the original curve. 

What should emerge from this lemma is the following picture: There is a disk $W$ centered at $\fxx_0$ and it is filled with two sets of curves: the level curves of $u$ and the trajectories $t\mapsto\fxx(t,\fxy)$. Through each point $\fxy\in W$, there is a unique trajectory $\fxx(t,\fxy)$ and a unique level line of $u$; furthermore, the vectors $(\partial\fxx/\partial t)(t,\fxy)$ and $Du(t,\fxx(t,\fxy))$ are collinear. This means that $(\partial\fxx/\partial t)(t,\fxy)$ is normal to the level line of $u$ at $(t,\fxy)$. This geometry explains the next definition.

\begin{definition}Given the conditions of Lemma 5.6, the trajectory $t\mapsto\fxx(t,\fxy)$ is called the normal flow starting from $(t_0,\fxy)$.
\end{definition} 

The following results are local, in the sense that we will always be looking at what happens in a neighborhood of a point $(t_0,\fxx_0)$ where the gradient of a function $u$ does not vanish. Also, the function $\fxx$ will mean the function $(t,\fxy)\mapsto\fxx(t,\fxy)$, where $\fxy$ is restricted to be on the level curve of $u$ that passes through $\fxx(t,\fxx_0)$. In other words, $\fxx(t,\fxy)$ is the family of level curves described above. We will also write this function as $\fxx(t,s)$, where s is an arc-length parameter for the level curve of $u$. The next few results relate a given evolution rule for $u$ with the corresponding evolution rule for its level curves $\fxx$.

\begin{proposition}Assume that the function $(t,\fxx)\mapsto u(t,\fxx)$ is $C^2$ in a neighborhood of $(t_0,\fxx_0)$ and that $Du(t_0,\fxx_0)\not=0$. Let $g:\RR\times\RR^+\to\RR$ be continuous and nondecreasing with respect to $\kappa$ and such that $g(-\kappa,t)=-g(\kappa,t)$. Then $u$ satisfies the curvature motion equation  
\begin{equation}\label{P581}
\frac{\partial u}{\partial t}(t,\fxx)=g({\rm curv}(u)(t,\fxx),t)|Du|(t,\fxx) 
\end{equation}
in a neighborhood of $(t_0,\fxx_0)$ if and only if the normal flow $t\mapsto\fxx(t,\cdot)$ satisfies the curvature equation 
\begin{equation}\label{P582}
\frac{\partial\fxx}{\partial t}(t,s)= g(\kappa(t,s),t)\fxn(t,s).
\end{equation} 
\end{proposition}

\begin{proof}We know from Lemmas 4.15 and 5.6 that there is a neighborhood of $N$ of $(t_0,\fxx_0)$ such that 
\begin{equation}\label{P583}
{\rm Curv}(\fxz)(t,s)=-{\rm curv}(u)(t,\fxx)\frac{Du}{|Du|}(t,\fxx)
\end{equation} 
and
\begin{equation}\label{P584}
\frac{\partial\fxx}{\partial t}(t,s)=-\Big(\frac1{|Du|}\frac{\partial u}{\partial t}\Big)\frac{Du}{|Du|}(t,\fxx(t,s))
\end{equation}
for $(t,\fxx)\in N$. An explanation of the notation is in order before proceeding with the proof, which is a direct consequence of \eqref{P583} and \eqref{P584}: The level curve of $u$ at scale $t$ and level $u(t_0,\fxx_0)$ is denoted by $\fxz(t,\cdot)$. For a given $t>0$, $s$ denotes an arc-length parameter for the curve $\fxz(t,\cdot)$. The point $\fxx$ appearing in the right-hand side of equation \eqref{P583} is the point on the curve $\fxz(t,\cdot)$ that corresponds to the value of $s$ appearing in the left-hand side of \eqref{P583}. The $s$ in equation \eqref{P584} represents the initial value of the normal flow, as previously explained following Lemma 5.6.

The first step is to choose the arc-length parameterization of $\fxz(t,\cdot)$ so the unit normal $\fxn={\bm\tau}^\perp$ is equal to $Du/|Du|$. Then,  
${\rm Curv}(\fxz)\cdot\fxn=-{\rm curv}(u)$ and $\kappa=-{\rm curv}(u)$. Assume that
\[
\frac{\partial u}{\partial t}=g({\rm curv}(u),t)|Du| 
\]
and substitute the right-hand side in \eqref{P584} to see that
\[
\frac{\partial\fxx}{\partial t}=-g({\rm curv}(u),t)\fxn
=-g(-\kappa,t)\fxn
=g(\kappa,t)\fxn,
\]
which is equation \eqref{P582}. For the other direction, assuming \eqref{P582} and substituting it in \eqref{P584} shows that
\[
-g({\rm curv}(u),t)\fxn=-\Big(\frac1{|Du|}\frac{\partial u}{\partial t}\Big)\frac{Du}{|Du|}=-\frac1{|Du|}\frac{\partial u}{\partial t}\fxn,
\]
which implies the scalar equation \eqref{P581}.
\end{proof}

\begin{corollary}Assume that the function $(t,\fxx)\mapsto u(t,\fxx)$ is $C^2$ in a neighborhood of $(t_0,\fxx_0)$ and that $Du(t_0,\fxx_0)\not=0$. Then $u$ satisfies the curvature motion equation 
\begin{equation}\label{eq68x}
\frac{\partial u}{\partial t}(t,\fxx)= {\rm curv}(u)(t,\fxx)|Du|(t,\fxx)
\end{equation}
in a neighborhood of $(t_0,\fxx_0)$ if and only if the normal flow $t\mapsto\fxx(t,\cdot)$ satisfies the intrinsic heat equation \eqref{eq61x},
\[
\frac{\partial\fxx}{\partial t}(t,s)=\frac{\partial^2\fxx}{\partial s^2}(t,s)={\rm Curv}(\fxx)(t,s).
\]
\end{corollary}

\begin{exercise}Check that all of the curvature equations mentioned in this section are contrast invariant. That is, assuming that $g$ is a real-valued $C^2$ function defined on $\RR$, show that the function $v$ defined by $v(t,\fxx)=g(u(t,\fxx))$ satisfies one of the equations $E$ if and only if $u$ satisfies $E$.
\end{exercise}

\subsection{Introduction to the affine curve and function equations}

There are two curvature equations that are affine invariant and are therefore particularly well suited for use in shape recognition.

\begin{definition}The image evolution equation
\begin{equation}\label{eq69x}
\frac{\partial u}{\partial t}(t,\fxx)= ({\rm curv}(u)(t,\fxx))^{1/3}|Du(t,\fxx)|
\end{equation}
is called affine morphological scale space (AMSS). The curve evolution equation 
\begin{equation}\label{eq610x}
\frac{\partial\fxx}{\partial t}(t,s)=|{\rm Curv}(\fxx)(t,s)|^{1/3}\fxn(t,s)\quad \Big(=\frac{{\rm Curv}(\fxx)(t,s)}{|{\rm Curv}(\fxx)(t,s)|^{2/3}}\Big)
\end{equation}
is called affine scale space (ASS). (For $x\in\RR$, $x^{1/3}$ will be defined to be ${\rm sign}(x)|x|^{1/3}$.)
\end{definition}

It is clear that AMSS and ASS are equivalent in the sense of Proposition  5.8. As one would expect from the names of these equations, they both have some sort of affine invariance. This is the subject of the next definition, the next two exercises, and the next section.

\begin{definition}We say that a curvature equation $E$ (image evolution equation) is affine invariant, if for every linear map $A$ with positive determinant, there is a positive constant $c=c(A)$ such that $(t,\fxx)\mapsto u(t,\fxx)$ is a solution of $E$ if and only if $(ct, A\fxx)\mapsto u(ct, A\fxx)$ is a solution of $E$.
\end{definition}

\begin{exercise}Assume that $(t,\fxx)\mapsto u(t,\fxx)$ is a $C^2$ function and that $A$ is a $2\times2$ matrix with positive determinant, which we denote by $|A|$. Define the function $v$ by $v(t,\fxx)=u(ct,A\fxx)$, where $c=|A|^{-2/3}$.
\begin{enumerate}[(i)]\setlength\itemsep{2pt} 
\item Prove that for each point $\fxx$ such that $Du(\fxx)\not={0}$ one has the relation
\[
{\rm curv}(v)(\fxx)|Dv(\fxx)|^3=|A|^2{\rm curv}(u)(A\fxx)|Du(A\fxx)|^3.
\]
\item Use (i) to deduce that the AMSS equation \eqref{eq69x} is affine invariant, that is, $(t,\fxx)\mapsto u(t,\fxx)$ is a solution of AMSS if and only $(t,\fxx)\mapsto v(t,\fxx)$ is a solution of \eqref{eq69x}. \finex
\end{enumerate}
\end{exercise}

\begin{exercise}This exercise is to show that the affine scale space (equation \eqref{eq610x}) is affine invariant. It relies directly on results from Exercise 4.2. Let $\sigma\mapsto \fxc(\sigma)$ be a $C^2$ curve, and assume that $|\fxc'(\sigma)|>0$. Then we know from Exercise 4.2 that
\begin{equation}\label{eq611x}
{\rm Curv}(\fxc)(\sigma)=\frac{1}{|\fxc'(\sigma)|^2}\left[\fxc''(\sigma)-\Bigg(\fxc''(\sigma)\cdot\frac{\fxc'(\sigma)}{|\fxc'(\sigma)|}\Bigg)\frac{\fxc'(\sigma)}{|\fxc'(\sigma)|}\right].
\end{equation}
Now assume that we have a family of $C^2$ Jordan arcs $(t,\sigma)\mapsto\fxc(t,\sigma)$. By projecting both sides of the intrinsic heat equation onto the unit vector $\fxc'^\perp/|\fxc'|$ and by using \eqref{eq611x}, we have the following equation:
\begin{equation}\label{eq612x}
\frac{\partial\fxc}{\partial t}\cdot\frac{\fxc'^\perp}{|\fxc'|}=\frac{\fxc''\cdot\fxc'^\perp}{|\fxc'|^3}
\end{equation}
We say that $\fxc$ satisfies a curvature equation if it satisfies equation \eqref{eq612x}. In the same spirit, we say that $\fxc$ satisfies an affine equation if for some constant $\gamma>0$
\begin{equation}\label{eq613x}
\frac{\partial\fxc}{\partial t}\cdot\fxc'^\perp=\gamma(\fxc''\cdot\fxc'^\perp)^{1/3}.
\end{equation}
\begin{enumerate}[(i)]\setlength\itemsep{2pt} 
\item Suppose that $\sigma=s$, an arc-length parameterization of $\fxc$. Show that equation \eqref{eq612x} can be written as
\[
\frac{\partial\fxc}{\partial t}={\rm Curv}(\fxc)+\lambda\tau, 
\]
where $\lambda$ is a real-valued function and $\tau$ is the unit tangent vector $\partial\fxc/\partial s$. (See the remark following equation \eqref{eq622x}.)
\item Let $A$ be a $2\times2$ matrix with positive determinant, and define the curve $\fxy$ by $\fxy(t,\sigma)=A\fxc(t,\sigma)$. We wish to show that if $\fxc$ satisfies an affine motion, then so does $\fxy$. As a first step, show that $A\fxx\cdot(A\fxy)^\perp=|A|\fxx\cdot\fxy$ and hence that $A(\fxx^\perp)\cdot(A\fxx)^\perp=|A||\fxx|^2$ for any $\fxx,\fxy\in\RR^2$.
\item Show that if $\fxc$ satisfies equation \eqref{eq613x}, then $\fxy$ satisfies
\[
\frac{\partial\fxy}{\partial t}\cdot\fxy'^\perp=\gamma|A|^{2/3}(\fxy''\cdot\fxy'^\perp)^{1/3}. \finex
\]
\end{enumerate}
\end{exercise}   

\subsection{The affine scale space as an intrinsic heat equation}

Suppose that for each scale $t$, $\sigma\mapsto\fxx(t,\sigma)$ is a Jordan arc (or curve) parameterized by $\sigma$, which is not in general an arc length. As in Chapter 4, we will denote the curvature of $\fxx$ by ${\bm \kappa}$. We wish to demonstrate a formal equivalence between the affine scale space,
\begin{equation}\label{eq615x}
\frac{\partial\fxx}{\partial t}=|{\bm \kappa}|^{1/3}\fxn(\fxx),
\end{equation} 
and an ``intrinsic heat equation''
\begin{equation}\label{eq616x}
\frac{\partial\fxx}{\partial t}=\frac{\partial^2\fxx}{\partial\sigma^2},
\end{equation} 
where $\sigma$ is a special parameterization called \textit{affine length}. We define an \textit{affine length parameter} of a Jordan curve (or arc) to be any parameterization $\sigma\mapsto\fxx(\sigma)$ such that 
\begin{equation}\label{eq617x}
[\fxx_\sigma,\fxx_{\sigma\sigma}]=1,
\end{equation}
where $[\fxx,\fxy]=\fxx^\perp\cdot\fxy$. If $s$ is an arc-length parameterization, then we have (Definition 4.2)
\begin{equation}\label{eq618x}
{\bm\tau}=\fxx_s\quad\fxn=|{\bm\kappa}|^{-1}\fxx_{ss}\quad\Big(=\frac{{\rm Curv(\fxx)}}{|{\rm Curv(\fxx)}|}\Big).
\end{equation} 
We also have
\begin{equation}\label{eq619x}
\fxx_\sigma=\fxx_s\frac{\partial s}{\partial\sigma}\quad\text{and}\quad\fxx_{\sigma\sigma}=\fxx_{ss}\Big(\frac{\partial s}{\partial\sigma}\Big)^2+\fxx_s\frac{\partial^2 s}{\partial\sigma^2}.
\end{equation}
Thus, 
\[
[\fxx_\sigma,\fxx_{\sigma\sigma}]=[\fxx_s,\fxx_{ss}]\Big(\frac{\partial s}{\partial\sigma}\Big)^3,
\]
and if \eqref{eq617x} holds, then
\[
[\fxx_s,\fxx_{ss}]\Big(\frac{\partial s}{\partial\sigma}\Big)^3=1.
\]
Since by \eqref{eq618x} $[\fxx_s,\fxx_{ss}]={\rm sign}([\fxx_s,\fxx_{ss}])|{\bm\kappa}|$, we conclude that
\begin{equation}\label{eq621x}
\frac{\partial s}{\partial\sigma}=({\rm sign}([\fxx_s,\fxx_{ss}])|{\bm\kappa}|)^{-1/3}.
\end{equation}

Substituting this result in the expression for $\fxx_{\sigma\sigma}$ shown in \eqref{eq619x} and writing $\fxx_s={\bm\tau}$, we see that
\[
\fxx_{\sigma\sigma}=|{\bm\kappa}|^{1/3}\fxn+\Big(\frac{\partial^2 s}{\partial\sigma^2}\Big){\bm\tau}.
\]
This tells us that equation \eqref{eq616x} is equivalent to the following equation:
\begin{equation}\label{eq622x}
\frac{\partial\fxx}{\partial t}=|{\bm\kappa}|^{1/3}\fxn+\Big(\frac{\partial^2 s}{\partial\sigma^2}\Big){\bm\tau}.
\end{equation}

Now it turns out that the graphs of the functions $\fxx$ that you get from one time to another do not depend on the term involving ${\bm\tau}$; you could drop this term and get the same graphs. More precisely, Epstein and Gage \cite{Epstein:1987:CSF} have shown that the tangential component of an equation like \eqref{eq622x} dose not matter as far as the geometric evolution of the curve is concerned. In fact, the tangential term just moves points along the curve itself, and the total curve evolution is determined by the normal term. As a consequence, equation \eqref{eq615x} is equivalent to equation \eqref{eq616x} in any neighborhood that avoids an inflection point, that is, in any neighborhood where $\fxn(\fxx)\not=0$. At an inflection point, ${\bm\kappa}=0$, and the two equations give the same result.

\section{Curvature motion in N dimensions}

We consider an evolution $(t,\fxx)\mapsto u(t,\fxx)$, where $\fxx\in\RR^N$ and $u(0,\cdot)=u_0$ is an initial $N$--dimensional image. Let $\kappa_i(u)(t,\fxx)$, $i=1,\ldots,N-1$, denote the $i^{\rm th}$ principal curvature at the point $(t,\fxx)$. (This is slightly different from the notation in section 4.6.) The mean curvature is by definition ${\rm curv}(u)=\sum_{i=1}^{N-1}\kappa_i$. We will now define three curvature motion flow equations in $N$ dimensions.

\paragraph*{Mean curvature motion.} This equation is a direct translation of equation \eqref{eq68x}:
\[
\frac{\partial u}{\partial t}=|Du|{\rm curv}(u).
\]
This says that the motion of a level hypersurface of $u$ in the normal direction is proportional to its mean curvature.

\paragraph*{Gaussian curvature motion for convex functions.} We say that a function is convex if all of its principal curvatures have the same sign. An example of such a function is the signed distance function to a regular convex shape. The equation is 
\[
\frac{\partial u}{\partial t}=|Du|\prod_{i=1}^{N-1}\kappa_i.
\]
The motion of a level hypersurface is proportional to the product of its principal curvatures, which is the Gaussian curvature. As we will see in Chapter 20, this must be modified before it can be applied to a nonconvex function.

\paragraph*{Affine-invariant curvature motion.} The equation is 
\[
\frac{\partial u}{\partial t}=|Du|\Big|\prod_{i=1}^{N-1}\kappa_i\Big|^{1/(N+1)}H\Big(\sum_{i=1}^{N-1}{\rm sign}(\kappa_i)\Big),
\]
where $H(N-1)=1$, $H(-N+1)=-1$, and $H(n)=0$ otherwise. The motion is similar to Gaussian curvature motion, but the affine invariance requires that the Gaussian curvature be raised to the power $1/(N+1)$. There is no motion at a point where the principal curvatures have mixed signs.

\section{Comments and references}

\paragraph*{Our definition of shape.} We have elected to define a shape as \textit{a compact set whose interior consists of the interiors of a finite number of rectifiable Jordan curves whose interiors are disjoint} because it presents an unambiguous picture relating a shape to its boundary curves and, conversely, the Jordan curves that are the boundary to the shape. There are, however, other ways to do this: If we were to define a shape as a compact set whose boundary is a finite set of Jordan curves that do not cross (whose interiors do not meet), then there are other ways to make the decomposition of the boundary into Jordan curves unambiguous, from both the mathematical and numerical points of view.  

The Italian mathematician Renato Caccioppoli proposed a theory of sets whose boundaries have finite length (finite Hausdorff measure). From his theory, it can be deduced that the boundary of a Caccioppoli set is composed of a countable number of Jordan curves, up to a set with zero length. 
This decomposition can even be made unambiguous. In other words, the set 
of Jordan curves associated with a given Caccioppoli set is unique and 
gives enough information to reconstruct the set 
\cite{ACMM2001}. This result justifies our focus on Jordan curves as the representatives of shapes. (For an account of the fascinating life of Caccioppoli we suggest a visit to 
http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Caccioppoli.html.)
  
\paragraph*{The role of curvature in shape analysis.} We mention the thesis by G. J. Agin \cite{Agin:1972:RDC} as being one of the first references dealing with the use of curvature for the representation and recognition of objects in computer vision. The now-classic paper by Asada and Brady \cite{Asada:1986:CPS} entitled ``The curvature primal sketch'' introduced the notion of computing a ``multiscale curvature'' as a tool for object recognition. (The title is an allusion to David Marr's famous ``raw primal sketch," which is a set of geometric primitives extracted from and representing an image.) The Asada--Brady paper led to a long series of increasingly sophisticated attempts to represent shape from curvature \cite{Dudek:1990:SRC,Dudek:1991:SRR} and to compute curvature correctly \cite{Mundy:1995:ORS}. 
 
\paragraph*{Affine-invariant curve shortening.} Affine-invariant geometry seems to have been founded by W. Blaschke. His three-volume work ``Vorlesungen {\"u}ber Differentialgeometrie'' (1921--1929) contains definitions of affine length and affine curvature. Curves with constant affine curvature are discussed in \cite{Maeda:1941:CPS}. The term ``affine shortening'' and the corresponding curve evolution equation were introduced by Sapiro and Tannenbaum in \cite{Sapiro:1993:AIS}. Some mathematical properties were developed by the same authors in \cite{Sapiro:1993:ICE} and \cite{Sapiro:1994:APC}. Angenent, Sapiro, and Tannenbaum gave the first existence and uniqueness proof of affine shortening in \cite{Angenent:1998:AHF}. 

\paragraph*{Curve shortening.} The mathematical study of the intrinsic heat equation (or curvature motion in two dimensions) was done is a series of brilliant papers in differential geometry between 1983 and 1987. We repeat a few of the titles, which indicate the progress: There was Gage \cite{Gage:1983:IIA} and Gage \cite{Gage:1984:CSM}: ``Curve shortening makes convex curves circular.'' Then there was Gage and Hamilton \cite{Gage:1986:HESa}: ``The heat equation shrinking convex plane curves.'' In this paper the authors showed that a plane convex curve became asymptotically close to a shrinking circle. In 1987 there was the paper by Epstein and Gage \cite{Epstein:1987:CSF}, and, in the same year, Grayson removed the convexity condition and finished the job \cite{Grayson:1987:HESb}: ``The heat equation shrinks embedded plane curves to round points.'' As the reviewer, U. Pinkall, wrote, ``This paper contains the final solution of the long-standing \textit{curve-shortening problem} for plane curves.''

The first papers that brought curve shortening (and some variations) to image analysis were by Kimia, Tannenbaum, and Zucker \cite{Kimia:1992:ECF} and by Mackworth and Mokhtarian \cite{Mackworth:1992:TMC}. Curve shortening was introduced as a way to do a multiscale analysis of curves, which were considered as shapes extracted from an image. In the latter paper, curve shortening was proposed as an efficient numerical tool for multiscale shape analysis.

\paragraph*{Mean curvature motion.} In his famous paper entitled ``Shapes of worn stones,'' Firey proposed a model for the natural erosion of stones on a beach \cite{Firey:1974:SWS}. He suggested that the rate of erosion of the surface of a stone was proportional to the Gaussian curvature of the surface, so that areas with high Gaussian curvature eroded faster than areas with lower curvature, and he conjectured that the final shape was a sphere. The first attempt at a mathematical definition of the mean curvature motion is found in Brakke \cite{Brakke:1978:MSM}. Later in the book, we will discuss the Sethian's clever numerical implementation of the same equation \cite{Sethian:1985:CEF}. Almgren, Taylor, Wang proposed a more general formulation of mean curvature motion that is applicable to crystal growth and, in general, to the evolution of anisotropic solids \cite{Fred:1993:CDF}.












 



























































































































































































