%gmChapt04.tex

\graphicspath{{./figures/chapter04/}}

\chapter{Level Lines and Level Surfaces}

This chapter contains the fundamentals of differential geometry that are used in Chapter 5 and elsewhere in the book. The development here and in Chapter 5 is a diversion from the continuous development in Chapters 3, 6, 7, 8, and 9. However, the material in this chapter and Chapter 5 is essential for the overall development of the theory, and we decided that the best place for it was between Chapters 3 and 6.

\section{Curves: tangents, normals, and curvature}

We summerize in this section the concepts and results about curves that are needed in this chapter and elsewhere in the book. The curves we considered will always be plane curves. A \textit{plane curve} $\Gamma$ is defined as the image of a continuous function $\fxz:[0,1]\to\RR^2$, $\fxz(t)=(x(t),y(t))$. This definition is much too general and includes objects such as Peano's space filling curve. Thus, we have two more-restrictive definitions: $\Gamma$ is a \textit{simple arc} or \textit{Jordan arc} if the mapping $\fxz:[0,1]\to\RR^2$ is one-to-one. We say that $\Gamma$ is a \textit{simple closed curve} or \textit{Jordan curve} if the mapping restricted to $(0,1)$ is one-to-one and if $\fxz(0)=\fxz(1)$. In other words, a Jordan arc is topologically equivalent to a closed interval, and a Jordan curve is topologically equivalent to a circle.

Recall that a Jordan arc (or curve) $\Gamma$ is said to be \textit{rectifiable} if the sums
\[
\sum_{i=1}^{n}|\fxz(t_i)-\fxz(t_{i-1})|
\]
taken over all partitions $0=t_0<t_1<\cdots<t_n=1$ are bounded. If this is the case, then by definition the \textit{length} of $\Gamma$ is the supremum of these sums. Saying that $\Gamma$ is rectifiable is equivalent to saying that the function $\fxz$ is of bounded variation. However, being rectifiable is an intrinsic property of $\Gamma$ and does not depend on the particular representation $\fxz$. If $\fxz$ is continuously differentiable on $[0,1]$, then it is of bounded variation and $\Gamma$ is rectifiable. Furthermore, we have the familiar integral that measures the arc length of the segment of the curve between $\fxz(s_0)$ and $\fxz(s_1)$:
\begin{equation}\label{arclength}
L(\fxz,s_0,s_1)=\int_{s_0}^{s_1}|\fxz'(t)|\,\rmd t=\int_{s_0}^{s_1}\sqrt{\fxz'(t)\cdot\fxz'(t)}\,\rmd t.
\end{equation}

The curves we deal with will always be rectifiable, and we generally want them to have some degree of smoothness. Furthermore, we want the definition of ``smoothness'' to describe an intrinsic property of $\Gamma$ rather than a property of some representation of $\Gamma$. If a function $\fxz$ representing $\Gamma$ is $C^1$, then the function $L$ in equation \eqref{arclength} has a derivative
\[
\frac{\rmd L}{\rmd s}=|\fxz'(s)|
\]
that is continuous. Nevertheless, the curve itself may not conform to our idea of being smooth, which at a minimum requires a tangent at every point $\fxy\in\Gamma$. For example, the motion of a point on the boundary of a unit disk as it rolls along the $x$-axis is described by $\fxz(\theta)=(\theta-\sin\theta, 1-\cos\theta)$, which is a $C^\infty$ function. Nevertheless, the curve has cusps at all multiples of $2\pi$. The problem is that $\fxz'(2k\pi)=0$. It is this sort of phenomena that motivates the definition of smoothness for curves.

\begin{definition} We say that a curve $\Gamma$ admits an arc-length parameterization $s\mapsto\fxz(s)$ if the function $\fxz$ is $C^1$ and ${\rmd L}/{\rmd s}=|\fxz'(s)|=1$ for all s. We say that $\Gamma$ is $C^m$, $m\in\mathbb N$, $m\geq1$, if the arc-length parameterization $\fxz$ is a $C^m$ function.
\end{definition}

An arc-length parameterization is also called a {\em Euclidian parameterization}. If a Jordan curve has an arc-length parameterization $\fxz$, then the domain of definition of $\fxz$ on the real line must be an interval $[a,b]$, where $b-a$ is the length of $\Gamma$, which we denote by $l(\Gamma)$. In this case, we will always take $[0,l(\Gamma)]$ as the domain of definition of $\fxz$. We identify $[0,l(\Gamma)]$ algebraically with the circle group by adding elements of $[0,l(\Gamma)]$ modulo $l(\Gamma)$.

\begin{definition}Assume that $\Gamma$ is $C^2$ and let $s\mapsto\fxz(s)$ be an arc-length parameterization. The tangent vector ${\bm\tau}$ is defined as ${\bm\tau}=\rmd\fxz/\rmd s$. The curvature vector of the curve $\Gamma$ is defined by ${\bm\kappa}=\rmd^2\fxz/\rmd s^2$. The normal vector $\fxn$ is defined by $\fxn={\bm\tau}^\perp$, where $(x,y)^\perp=(-y,x)$.
\end{definition}

\begin{exercise}Let $\Gamma$ by a Jordan arc parameterized by $\fxx:[0,1]\to\Gamma$ and by $\fxy:[0,1]\to\Gamma$. Show that $\fxx=\fxy(f)$ or $\fxx=\fxy(1-f)$, where $f$ is a continuous, strictly increasing function that maps $[0,1]$ onto $[0,1]$. Hint: $\fxx$ and $\fxy$ are one-to-one, and since $[0,1]$ is compact, they are homeomorphisms. Thus, $\fxy^{-1}(\fxx)=f$ is a one-to-one continuous mapping of $[0,1]$ onto itself. \finex
\end{exercise}

If a Jordan arc $\Gamma$ is $C^1$, then the result of Exercise 1 implies that there are only two arc-length parameterizations of $\Gamma$: If $\fxx:[0,l(\Gamma)]\to\Gamma$ is an arc-length parameterization of $\Gamma$ and $\fxy$ is another one, then either $\fxy(s)=\fxx(s)$ or $\fxy(s)=\fxx(l(\Gamma)-s)$, $s\in[0,l(\Gamma)]$. Here is a proof: >From Exercise 1 we know that a continuous, strictly increasing function $f$ exists such that $\fxx=\fxy(f)$ or $\fxx=\fxy(l(\Gamma)-f)$. Assume that $\fxx=\fxy(f)$. Then $\fxx(0)=\fxy(0)$. By the definition of arc-length parameterization, the distance along $\Gamma$ from $\fxx(0)$ to $\fxx(s)$ is $s$, and the distance from $\fxy(0)$ to $\fxy(f(s))$ is $f(s)$. If $\fxx=\fxy(f)$, then we must have $f(s)=s$. A similar argument works if we assume that $\fxx=\fxy(l(\Gamma)-f)$.

The argument is slightly more involved in case $\Gamma$ is a Jordan curve, since in this case we are dealing with the topology of the circle rather the closed interval. We state this as a proposition.

\begin{proposition}Suppose that $\Gamma$ is a $C^1$ Jordan curve with arc-length parameterization $\fxx:[0,l(\Gamma)]\to\Gamma$. Then any other arc-length parameterization $\fxy:[0,l(\Gamma)]\to\Gamma$ is of the form $\fxy(s)=\fxx(s+\sigma)$ or $\fxy(s)=\fxx(-s+\sigma)$ for some $\sigma\in[0,l(\Gamma)]$.
\end{proposition}
\begin{proof}Recall that addition is modulo $l(\Gamma)$. The functions are one-to-one, so there is a unique $\sigma$ in $[0,l(\Gamma))$ such that $\fxy(0)=\fxx(\sigma)$. Define $\fxx_{\sigma}$ by $\fxx_{\sigma}(s)=\fxx(s+\sigma)$. Take $0<a<l(\Gamma))/2$ and consider the two arcs $\gamma_{\fxx_{\sigma}}=\fxx_{\sigma}([-a,a])$ and $\gamma_{\fxy}=\fxy([-a,a])$. These are Jordan arcs in $\Gamma$. In fact, since $\fxx_{\sigma}$ and $\fxy$ are both arc-length parameterizations and since $\fxx_{\sigma}(0)=\fxy(0)$, it follows that $\gamma_{\fxx_{\sigma}}=\gamma_{\fxy}$. This being the case, the arguments given above for Jordan arcs apply, and we conclude that $\fxy(s)=\fxx_{\sigma}(s)$ or  $\fxy(s)=\fxx_{\sigma}(-s)$, for $s\in[-a,a]$. Since the functions are continuous and $l(\Gamma)$-periodic, and since we can take $a$ as near to $l(\Gamma))/2$ as we wish, the result holds for all $s\in\RR$.
\end{proof}

\begin{proposition}Let $\Gamma$ be a $C^2$ Jordan arc or curve, and let $\fxx$ and $\fxy$ by any two arc-length parameterizations of $\Gamma$.
\begin{enumerate}[$(i)$]\setlength\itemsep{2pt}
\item If $\fxx(s)=\fxy(t)$, then $\fxx'(s)=\pm\fxy'(t)$.
\item The vector $\bm{\kappa}$ is independent of the choice of arc-length
parameterizations and it is orthogonal to $\bm{\tau}=\fxx'$.
\end{enumerate}
\end{proposition}
\begin{proof}In case $\Gamma$ is a Jordan curve, $\fxy(s)=\fxx(\pm s+\sigma)$ by Proposition 4.3, and $(i)$ follows by differentiation. This is also geometrically obvious: $\fxx'(s)$ and $\fxy'(t)$ are unit vectors tangent to $\Gamma$ at the same point. Thus, they either point in the same direction they point in opposite directions. In the case of a Jordan arc, we have $\fxy(s)=\fxx(s)$ or $\fxy(s)=\fxx(l(\Gamma)-s)$, and differentiation gives the result. Of course, in this case, we have one-sided derivatives at the end points.

Using any of the above representations and differentiating twice shows that $\fxx''=\fxy''$. Since $\fxx'\cdot\fxx'=1$, differentiating this expression shows that $\fxx''\cdot\fxx'=0$. Thus, $\fxx''$ and $\fxx'$ are orthogonal and $\fxx''$ and $\fxx'^\perp$ are collinear.
\end{proof}

The curvature vector has been defined in terms of the arc length. Curves, however, are often naturally defined in terms of other parameters. The next two exercises develop the differential relations between an arc-length parameterization and an other parameterization.

\begin{exercise}Assume that $\Gamma$ is a $C^2$ Jordan arc or curve. Let $s\mapsto\fxx(s)$ be an arc-length parameterization and let $t\mapsto\fxy(t)$ be any other parameterization with the property that $\fxy'(t)\not=0$. Since $\fxx$ and $\fxy$  are one-to-one, we can consider the function $\fxy^{-1}(\fxx)=\varphi$. Then $\fxx(s)=\fxy(\varphi(s))$, where $\varphi(s)=t$. The inverse function $\varphi^{-1}$ is given by
\[
s=\varphi^{-1}(t)=\int_{t_0}^t \sqrt{\fxy'(r)\cdot\fxy'(r)}\,\rmd r,
\]
so we know immediately that $\varphi^{-1}$ is absolutely continuous with continuous derivative equal to $\sqrt{\fxy'(t)\cdot\fxy'(t)}$. Thus, we also know that $\varphi'(s)=|\fxy'(\varphi(s))|^{-1}$. Note that we made a choice above by taking $\sqrt{\fxy'(r)\cdot\fxy'(r)}$ to be positive. This is equivalent to assuming that $\fxx'(s)$ and $\fxy'(\varphi(s))$ point in the same direction or that $\varphi'(s)>0$.
\begin{enumerate}[(i)]\setlength\itemsep{2pt}
\item Show that $\bm{\kappa}(s)=\fxx''(s)=\fxy''(\varphi(s))[\varphi'(s)]^2+\fxy'(\varphi(s))\varphi''(s)$ and deduce that
\[
\varphi''(s)=-\frac{\fxy''(\varphi(s))\varphi'(s)\cdot\fxy'(\varphi(s))}{|\fxy'(\varphi(s))|^3}=-\frac{\fxy''(\varphi(s))\cdot\fxy'(\varphi(s))}{|\fxy'(\varphi(s))|^4}.
\]
\item Use the results of (i) to show that
\begin{equation}\label{eq41}
\bm{\kappa}(s)=\fxx''(s)=\frac{1}{|\fxy'(t)|^2}\left[\fxy''(t)-\Bigg(\fxy''(t)\cdot\frac{\fxy'(t)}{|\fxy'(t)|}\Bigg)\frac{\fxy'(t)}{|\fxy'(t)|}\right],
\end{equation}
where $\varphi(s)=t$. Show that we get the same expression for the right-hand side of \eqref{eq41} with the assumption that $\varphi'(s)<0$. This shows that the curvature vector $\bm{\kappa}$ does not depend on the choice of parameter.
\item Consider the scalar function $\kappa(\fxy)$ defined by $\kappa(\fxy)(s)={\bm\kappa}(s)\cdot\fxx'(s)^\perp$. Use equation \eqref{eq41} to show that
\[
\kappa(\fxy)(t)=\frac{\fxy''(t)\cdot[\fxy'(t)]^{\perp}}{|\fxy'(t)|^3}
\]
Note that $\kappa(\fxy)$ is determined up to a sign that depends on
the sign of $\varphi'(s)$; however, $|\kappa(\fxy)|=|{\bm\kappa}|$ is uniquely determined. \finex
\end{enumerate}
\end{exercise}

\begin{exercise}Assume that $\Gamma$ is a Jordan arc or curve that is represented by a $C^1$ function $t\mapsto\fxx(t)$ with the property that $\fxx'(t)\not=0$. Prove that $\Gamma$ is $C^1$.
\end{exercise}

\begin{exercise}\leavevmode
\begin{enumerate}[(i)]\setlength\itemsep{2pt}
\item Consider the arc-length parameterization of the circle with radius $r$ centered at the origin given by $\fxx(s)=(r\cos(s/r), r\sin(s/r))$. Show that the length of the curvature vector is $1/r$.
\item Compute the scalar curvature of the graph of $y=(a/2)x^2$ at $x=0$.
\finex
\end{enumerate}
\end{exercise}

The generalization of this last exercise is essential for work that follows, particularly for studying the properties of curves that are presented to us as level lines of functions $u:\RR^2\to\RR$. Assume we are given a $C^1$ Jordan arc $\Gamma$ and an arc-length parameterization $\fxc$ in a neighborhood of $\fxc(s_0)\in\Gamma$. We assume, without loss of generality, that $s_0=0$ and that $\fxc(0)=0$. Then we can establish a local coordinate system based on the two unit vectors $\fxc'(0)$ and $\fxc'(0)^\perp$, where the $x$-axis is positive in the direction of $\fxc'(0)$. If we write $\fxc(s)=(x(s),y(s))$ in this coordinate system, then
\begin{align*}
x(s)&=\fxc(s)\cdot\fxc'(0),\\
y(s)&=\fxc(s)\cdot\fxc'(0)^\perp.
\end{align*}
Since $\rmd x/\rmd s(s)=\fxc'(s)\cdot\fxc'(0)$, $\rmd x/\rmd s(0)=1$. Then the inverse function theorem implies the existence of a $C^1$ function $g$ and a $\delta>0$ such that $s=g(x)$ for $|x|<\delta$. This means that, for $|x|<\delta$, $\Gamma$ is represented locally by the graph of the $C^1$ function $f$, where $f(x)=y(g(x))=\fxc(g(x))\cdot\fxc'(0)^\perp$. To be slightly more precise, denote the graph of $f$ for $|x|<\delta$ by $\Gamma_f$. Since $g$ is one-to-one, $\Gamma_f$ is a homeomorphic image of the open interval $(-\delta,\delta)$ and $\Gamma_f\subset\Gamma$. If $\Gamma$ is $C^2$, then $f$ is $C^2$ and $f''(0)=\fxc''(0)\cdot\fxc'(0)^\perp$.

Conversely, given a $C^1$ function $f$, we can consider the graph $\Gamma_f$ of $f$ in a neighborhood of the origin. Then $\Gamma_f$ is represented by $\fxc$, where $\fxc(x)=(x,f(x))$. We may assume that $f(0)=0$ and $f'(0)=0$ (by a translation and rotation if necessary). Then arc-length along $\Gamma$ is measured by
\[
s(x)=\int_0^x\sqrt{1+[f'(t)]^2}\,\rmd t,
\]
and $\rmd s/\rmd x=\sqrt{1+[f'(x)]^2}$. This time there is a $C^1$ function $h$ such that $h(s)=x$ and $h'(s)=(1+[f'(h(s))]^2)^{1/2}$. Then $\Gamma$ is represented by $\tilde\fxc(s)=(h(s), f(h(s)))$. Short computations show that $|\tilde\fxc'(s)|=1$. If $f$ is $C^2$, then $\Gamma$ is $C^2$ and $\tilde\fxc''(0)\cdot\tilde\fxc'(0)^\perp=f''(0)$. Thus we have the following result: A $C^1$ Jordan arc $\Gamma$ can be represented locally as the graph of a $C^1$ scalar function $f$. Conversely, the graph of a $C^1$ function is a $C^1$ Jordan arc.

This is all we need to say about Jordan arcs and curves for this and the next chapter. Further results about Jordan curves, which are needed for the axiomatic theory of shape scale spaces (Chapter 19), are given in Appendix A.

\section{The level-line structure (or topographic map) of an image}

We saw in Chapter 3 how an image can be represented by its level sets. The next step, with a view toward shape analysis, is the representation of an image in terms of its level lines. We rely heavily on the implicit function theorem to develop this representation. We begin with a two-dimensional version. The statement here is just a slight variation on the implicit function theorem quoted in section I.4 of the Introduction.

\begin{theorem}Let $u$ be a real-valued $C^1$ function defined on an open set $\Omega\subset\RR^2$. Assume that $Du(\fxx_0)\ne0$ at $\fxx_0=(x_0,y_0)$ in $\Omega$. Let $\bm{i}$ denote the unit vector in the direction $(u_x,u_y)$, let $\bm{j}$ denote the unit vector in the orthogonal direction $(-u_y,u_x)$, and write $\fxx=\fxx_0+x\bm{i}+y\bm{j}$. Then there is a disk $D(\fxx_0, r)$ and a unique $C^1$ function $\varphi$, $\varphi:[-r,r]\to\RR$, such that if $\fxx\in D(\fxx_0, r)$, then
\[
u(x,y)=0\quad \Longleftrightarrow\quad x=\varphi(y).
\]
\end{theorem}

If $Du(\fxx_0)\ne0$, then Theorem 4.5 ensures that there is a disk $D(\fxx_0, r)$ such that the set $\{\fxx\mid u(\fxx)=u(\fxx_0), \fxx\in D(\fxx_0, r) \}$ is a $C^1$ Jordan arc that is the graph of a unique $C^1$ function. The following corollary is a global version of this local result.

\begin{corollary}Assume that $u\in C^1(\RR^2)$ and let $u^{-1}(\lambda)=\{\fxx\mid u(\fxx)=\lambda\}$ for $\lambda\in\RR$. If $u^{-1}(\lambda)(\not=\emptyset)$ is compact and if $Du(\fxx)\ne0$ for all $\fxx\in u^{-1}(\lambda)$, then $u^{-1}(\lambda)$ is a finite union of disjoint Jordan curves.
\end{corollary}
\begin{proof}From Theorem 4.5 we know that for each point $\fxx\in u^{-1}(\lambda)$ there is a neighborhood $D(\fxx,r(\fxx))$ such that $D(\fxx,r(\fxx))\cap u^{-1}(\lambda)$ is a $C^1$ Jordan arc. Since $u^{-1}(\lambda)$ is compact, there are a finite number of point $\fxx_i$, $i=1,\ldots,m$, such that $u^{-1}(\lambda)\subset\bigcup_{i=1}^mD(\fxx_i,r(\fxx_i))$. This implies that $u^{-1}(\lambda)$ is a finite union of Jordan arcs and hence has a finite number of connected components. Let $\Gamma$ be one of these components. We wish to prove that $\Gamma$ is a Jordan curve, and here are the ingredients we have to do this.

There is a finite number of $C^1$ Jordan arcs $\Gamma_j$, $j=1,\ldots,n$, such that $\Gamma=\bigcup_{j=1}^n\Gamma_j$. Each arc $\Gamma_j$ can be represented by a $C^1$ arc-length parameterization $\fxc_j$. The functions $\fxc_j$ are homeomorphisms, and the domain of definition of $\fxc_j$ may be chosen to be any interval $I_j=(a_j,b_j)$ such that $b_j-a_j=l(\Gamma_j)$, the length of $\Gamma_j$. The connected component $\Gamma$ is closed (hence compact), so the points $\fxc_j(a_j)$ and $\fxc_j(b_j)$ are also in $\Gamma$. The $\Gamma_j$ were originally given as the graphs of $C^1$ functions $\varphi_j$ defined on a local coordinate system, so we are assured that $\fxc_j(a_j)\ne\fxc_j(b_j)$ and hence that $\fxc_j:[a_j,b_j]\to\overline\Gamma_j$ is also a homeomorphism. By partially ordering the $\Gamma_j$ and denoting the maximal elements by $\Gamma_{m(j)}$, we see that $\Gamma=\bigcup_{j=1}^n\Gamma_{m(j)}$. Thus, we may assume that the $\Gamma_j$ are all maximal and, hence, that $\Gamma_i\not\subset\Gamma_j$ if $i\ne j$. We are now ready to prove the result.

Note first that $n\geq2$: $\Gamma$ is compact and $\Gamma_1$ is not. We begin by assuming that $n>2$. Since $\Gamma$ is connected, $\Gamma_1$ must intersect one of the other arcs, which, by renumbering if necessary, we call $\Gamma_2$. Let $\fxx$ be any point in $\Gamma_1\cap\Gamma_2$. Then there are two (unique) points $s\in I_1$ and $t\in I_2$ such that $\fxc_1(s)=\fxc_2(t)$. By Proposition 4.3, we may assume that $\fxc'_1(s)=\fxc'_2(t)$. Since we can change the domain $I_2$ as long as we retain the length of the interval $b_2-a_2$, we may assume that $s=t$ and that the two intervals $I_1=(a_1,b_1)$ and $I_2=(a_2,b_2)$ and $s$ are such that
\[
a_1<a_2<s<b_1<b_2.
\]

Now focus on the fact that $\fxx\in\Gamma_1\cap\Gamma_2$. The curves $\Gamma_1$ and $\Gamma_2$ that pass through $\fxx$ are the graphs of functions $\varphi_1$ and $\varphi_2$ that satisfy $\varphi_j(y)=x$, $\fxx=(x,y)$, and $u(\varphi_j(y),y)=\lambda$, $j=1,2$. Theorem 4.2 states that, in some neighborhood of $\fxx$, these functions are unique. This means that the two curves  $\Gamma_1$ and $\Gamma_2$ must agree is some neighborhood of $\fxx$, and this in turn implies that $\fxc_1(t)=\fxc_2(t)$ for $t$ is some open interval containing $s$. Now let $t_0=\sup\{t\mid a_2<t<b_1,\fxc_1(t)=\fxc_2(t)\}$. Then the argument just given shows that $t_0=b_1$: If $t_0<b_1$, then there is a neighborhood of $\fxc_1(t_0)=\fxc_2(t_0)$ in which $\Gamma_1$ and $\Gamma_2$ agree, which implies that there are $t>t_0$ where
$\fxc_1(t)=\fxc_2(t)$. The same argument proves that $\inf\{t\mid a_2<t<b_1,\fxc_1(t)=\fxc_2(t)\}=a_2$. This proves that $\fxc_1(t)=\fxc_2(t)$ for $t\in[a_2,b_1]$ and allows us to define the function $\fxc_{12}$ on $(a_1,b_2)$ by $\fxc_{12}(t)=\fxc_1(t)$ for $t\in(a_1,b_1)$ and $\fxc_{12}(t)=\fxc_2(t)$ for $t\in(a_2,b_2)$. The function $\fxc_{12}$ is one-to-one on $(a_1,b_1)$ and it is one-to-one on $(a_2,b_2)$. If $\fxc_{12}$ is one-to-one on all of $(a_1,b_2)$, then $\Gamma_1\cup\Gamma_2=\Gamma_{12}$ is a Jordan arc and $\Gamma=\Gamma_{12}\cup\big(\bigcup_{j=3}^n\Gamma_j\big)$.

Here is what we have shown so far: If $n>2$ and if $\fxc_{12}$ is one-to-one on $(a_1,b_2)$, then $\Gamma$ is the union of $n-1$ Jordan arcs. Now repeat the process, beginning by partially ordering the remaining Jordan arcs and then retaining only those that are maximal. After at most $n-2$ steps, there will be only two arcs remaining. (Note that repeating the process cannot reduce $n$ to one, since the remaining arc would not be compact.)

We arrive at the following situation: $\Gamma=\Gamma_1\cup\Gamma_2$, $\Gamma_1\not\subset\Gamma_2$, and $\Gamma_2\not\subset\Gamma_1$. The arcs are represented by arc-length parameterizations $\fxc_1:(a_1,b_1)\to\Gamma_1$ and $\fxc_2:(a_2,b_2)\to\Gamma_2$ with $a_1<a_2<b_1<b_2$. This time, the function $\fxc_{12}$, which agrees with $\fxc_1$ on $(a_1,b_1)$ and $\fxc_2$ on $(a_2,b_2)$, cannot be one-to-one on all of $(a_1,b_2)$ because $\Gamma$ is compact. Consequently, there are points $s$ and $t$ such that $\fxc_{12}(s)=\fxc_{12}(t)$ and $a_1<s\leq a_2<b_1\leq t<b_2$. An argument given above using the uniqueness  of level curves passing through a point, which here is $\fxy=\fxc_{12}(s)=\fxc_{12}(t)$, proves that the arcs $\Gamma_1$ and $\Gamma_2$ must coincide on the sets $[a_1,s]$ and $[t,b_2]$. We are going to remove the overlapping parts of the curves that are not needed for representing $\Gamma$. Thus, define $\tilde\Gamma_1=\fxc_1[s,a_2]$ and $\tilde\Gamma_2=\fxc_2[a_2,t]$. Then $\Gamma=\tilde\Gamma_1\cup\tilde\Gamma_2$, $\fxc_{12}$ is one-to-one on $(s,a_2)$ and one-to-one on $(a_2,t)$, and $\fxc_{12}(s)=\fxc_{12}(t)$. The function $\fxc_{12}$ is a $C^1$ arc-length parameterization of $\Gamma$ with $|\fxc_{12}'(x)|=1$ for all $x\in[s,t]$. It remains only to show that $\fxc_{12}$ is one-to-one on $(s,t)$. If this is not the case, there are two points $p$ and $q$ such that $p<q$ and $\fxc_{12}(p)=\fxc_{12}(q)$. We have argued above, and this is the key to the proof, that in such a situation the curves passing through the point
$\fxy=\fxc_{12}(p)=\fxc_{12}(q)$ must coincide ``as far as possible,'' which in this case means on the interval $[p,q]$. This, however, implies that there is a discontinuity in $\fxc'$ at the point $(p+q)/2$, so we must conclude that $\fxc_{12}$ is one-to-one on $(s,t)$, and, hence, that $\Gamma$ is a Jordan curve.
\end{proof}

\begin{exercise}For those readers well versed in the theory of differentiable manifolds, the last proof my seem naive. For those who are not well versed, we suggest filling in the omitted details.
\end{exercise}


The next theorem is one of the results that we are going to quote rather than prove, as we have done with the theory of integration and the implicit function theorem, and as we will do with the Jordan curve theorem in the next section.

\begin{theorem}[Sard's theorem] Assume that $u:\RR^N\to\RR$ is $C^1$ and has compact support. Then for almost every $\lambda$ in the range of $u$, the set $u^{-1}(\lambda)$ is nonsingular, which means that for all $\fxx\in u^{-1}(\lambda)$, $Du(\fxx)\ne0$.
\end{theorem}

Recall that in section 1.2 we began with a function $u$ defined on $[0,1]^N$ and extended it first by symmetry to $C=[-1,1]^N$ and then by periodicity to all of $\RR^N$. The resulting function was called $C$-periodic and symmetric. We are concerned in the next result with functions defined on $\RR^2$ that are $C^1$ and $C$-periodic, where $C=[-1,1]^2$.

We assume that $u:\RR^2\to\RR$ is $C$-periodic and $C^1$. To apply Sard's we need to have the support of $u$ compact, but this is the case, since the ``$C$-periodic topology'' is just the topology of the two-dimensional torus $\mathbb T^2$. Thus, $u^{-1}(\lambda)$ is nonsingular for almost every $\lambda$ in the range of $u$. If $\lambda$ is such that $u^{-1}(\lambda)$ is nonsingular, then we can interpret Corollary 4.6 in the $\mathbb T^2$-context and conclude that $u^{-1}(\lambda)$ is a finite set of simple closed curves on $\mathbb T^2$. We state this result as a corollary.

\begin{corollary}Let $u:\RR^2\to\RR$ be $C^1$ and $C$-periodic. Then for almost every $\lambda$ in the range of $u$, the set $u^{-1}(\lambda)$ is the union of $C^1$ curves. Viewed on $\mathbb T^2$, $u^{-1}(\lambda)$ is a finite set of disjoint simple closed curves.
\end{corollary}

When viewed in $\RR^2$, there can be two kinds of $C^1$ curves: Jordan curves and curves that extend to infinity. These sets are, of course, $C$-periodic.

\section{The topographic map as a complete image representation}

The sole purpose of this section is to convince the reader that the level lines of a function provide a faithful representation of the function, in the sense that it is possible, at least theoretically, to reconstruct the function from its level lines. We will argue this for the case $u$ is a $C^1$ function on $\RR^2$ with compact support, and we will comment on other cases. The result that allows us to prove this special case is the Jordan curve theorem, which we quote.

\begin{theorem}[Jordan curve theorem]Let $\Gamma$ be a Jordan curve, that is, $\Gamma$ is the image in $\RR^2$ of a continuous mapping $\fxz:[0,1]\to\RR^2$ such that $\fxz$ is one-to-one on $(0,1)$ and $\fxz(0)=\fxz(1)$. Then $\RR^2\setminus\Gamma$ consists of two open, connected components, one bounded and the other unbounded.
\end{theorem}

We denote the bounded component of $\RR^2\setminus\Gamma$ by $\gamma$ and the unbounded component by $g$, and we refer to $\gamma$ as the interior of $\Gamma$ and to $g$ as the exterior. Similarly, if we have a number of curves $\Gamma_i$, $i=1,\ldots,n$, then $\gamma_i$ and $g_i$ denote the bounded and unbounded components of $\RR^2\setminus\Gamma_i$ respectively.

Here is another result that is essential for our argument; it can be considered a generalization of the Jordan curve theorem.

\begin{proposition}If $\Omega$ is an open, connected set in $\RR^2$ and if $\Gamma\subset\Omega$ is a Jordan curve, then $\Omega\cap\gamma$ and $\Omega\cap g$ are also open and connected.
\end{proposition}

In particular, this says that removing Jordan curves and their interiors does not disconnect an open, connected set. This will allow us to assign an orientation to the level lines of a $C^1$ function.

Suppose that $u$ is a $C^1$ function on $\RR^2$ with compact support. We know from Sard's theorem and Corollary 4.6 that for almost every $\lambda$ in the range of $u$, $u^{-1}(\lambda)$ is a finite union of disjoint Jordan curves, which we call $\Gamma_i$, $i=1,\ldots,n$. The plan is to show that the level sets of $u$, $\levelset_{\lambda}u$, can be represented in terms of the $\Gamma_i$, $\gamma_i$, and $g_i$ for a dense set of $\lambda$'s, that is, for the nonsingular $\lambda$'s in the range of $u$. It then follows from Lemma 3.8 that $u(\fxx)=\sup\{\lambda\mid\fxx\in\levelset_{\lambda}u\}$ for almost every $\fxx\in\RR^2$.

Note that the $\gamma_i$ are partially ordered by inclusion. This in turn partially orders the curves $\Gamma_i$: $\Gamma_i\prec\Gamma_j$ if and only if $\gamma_i\subset\gamma_j$. Thus we can think of the $\Gamma_i$ as forming a finite number of disjoint trees. For convenience of discussion, we will say that the maximal elements of these trees are at level 1, that the curves just below are at level 2, and so on. Given a curve $\Gamma_i$ at, say, level $k$, there may or may not be any elements inside $\Gamma_i$ at level $k+1$. If there are curves $\Gamma_j$ inside $\Gamma_i$ at level $k+1$, then we know from Proposition 4.10 that $\gamma_i\setminus\bigcup_j(\Gamma_j\cup\gamma_j)=\gamma_i\setminus\bigcup_j\overline{\gamma}_j$ is open and connected. This implies that either $u(\fxx)>\lambda$ for $\fxx\in\gamma_i\setminus\bigcup_j\overline{\gamma}_j$ or $u(\fxx)<\lambda$ for $\fxx\in\gamma_i\setminus\bigcup_j\overline{\gamma}_j$. (Recall that $u^{-1}(\lambda)=\cup_i\Gamma_i$.) In the first case we say that $\Gamma_i$ has \textit{positive orientation} and in the second case that $\Gamma_i$ has \textit{negative orientation}.

Observe that the maximal elements, the curves $\Gamma_m$ at the top of the trees, all have the same orientation. This is because $\RR^2\setminus\bigcup_m\overline{\gamma}_m$ is open and connected. Thus, either $u(\fxx)>\lambda$ on  $\RR^2\setminus\bigcup_m\overline{\gamma}_m$, in which case the $\Gamma_m$ have negative orientation, or $u(\fxx)<\lambda$ on  $\RR^2\setminus\bigcup_m\overline{\gamma}_m$, and the $\Gamma_m$ have positive orientation.

To represent $\levelset_{\lambda}u$, we need to consider two cases: The maximal curves all have positive orientation, or the maximal curves all have negative orientation. In the first case, we have the following representation for $\levelset_{\lambda}u$:
\begin{equation}\label{LSET}
\levelset_{\lambda}u=\bigcup_p\Big(\overline{\gamma}_p\setminus\big(\cup_j\gamma_j\big)\Big),
\end{equation}
where the first union is taken over all $p$ such that $\Gamma_p$ has positive orientation and the second union is taken over all $j$ such that
$\gamma_j\subset\gamma_p$ and level$(\gamma_j)=$ level$(\gamma_p)+1$.

\begin{figure}[!t]
\setkeys{Gin}{width=5cm}
\centerline{
\includegraphics{fig04.01.1.eps}
\includegraphics{fig04.01.2.eps}
}
\caption[Level lines]{\label{fig41}Level lines as a complete representation of the shapes present in an image. All level lines of the image of a sea bird for levels that are multiples of 12 are displayed. Notice that we do not need a previous smoothing to visualize the shape structures in an image: It is sufficient to quantize the displayed levels.}
\end{figure}

IIf the maximal curves all have negative orientation, then the set $\bigcap_{m}\overline{g}_m$ must be added to the right-hand side of \eqref{LSET}:
\begin{equation}\label{LSETT}
\levelset_{\lambda}u=\Bigg(\bigcup_p\Big(\overline{\gamma}_p\setminus\big(\cup_j\gamma_j\big)\Big)\Bigg)\cup\Big(\bigcap_{m}\overline{g}_m\Big),
\end{equation}
where the union indexed by $m$ is taken over all maximal curves.

We hope that this discussion has persuaded the reader of the truth of the following result.

\begin{proposition}Let $u$ be a $C^1$ function with compact support defined on $\RR^2$. Then $u$ can be recovered (a.e.) from its level lines.
\end{proposition}

In fact, we have shown that $u$ can be recovered from the level lines $u^{-1}(\lambda)$ for which $\lambda$ is nonsingular in the sense of Sard's theorem. We define the \textit{topographic map} of $u$ to be the mapping $\lambda:\RR\mapsto u^{-1}(\lambda)$, where $\lambda$ is nonsingular. Thus another way to state Proposition 4.11 is that $u$ can be recovered from its topological map. Note also that Proposition 4.11 holds under the weaker assumption that $u(\fxx)$ tends to some limit as $|\fxx|\to+\infty$.

In practice, we are faced with a digital image defined on a rectangular grid, and as we have argued elsewhere, these digital images can be interpolated several ways to produce a good rendition of the ``original'' image. The properties of the level lines of the interpolated function clearly depend on the kind of interpolation. To avoid discussing the different cases and topological discussions that take us too far afield, we are going to make rather specific assumptions about the level lines in the next proposition.

\begin{proposition}Let $u$ be a real-valued function defined on a closed rectangle $R\in\RR^2$. Assume that, for a dense set of $\lambda$'s in the range of $u$, the set $u^{-1}(\lambda)$ consists of a finite number of disjoint Jordan arcs and curves. Assume further that the Jordan curves are in the interior of $R$ and that the Jordan arcs terminate on the boundary of $R$. Then $u$ can be recovered from its topographic map.
\end{proposition}
\begin{proof}We will, in fact, give only an outline of a proof: Many details will be omitted.


Assume that there are $k$, $k\geq0$, Jordan arcs that terminate on the boundary of $R$. It follows from the Jordan curve theorem that the these arcs partition the interior of $R$ into $k+1$ simply connected open sets. Denote these sets by $R_i$, $i=1,\dots,k+1$.

We treat each $R_i$ separately. Here, a given $R_i$ plays essentially the same role that $\RR^2$ played in the argument given for the case $u$ had compact support. Let $\Gamma_{i,j}$ denote the Jordan curves in $R_i$. Then the set $R_i\setminus\bigcup_m(\Gamma_{i,m}\cup\gamma_{i,m})$, where the $\Gamma_{i,m}$ are the maximal elements in $R_i$, is open and connected. Thus, $u(\fxx)>\lambda$ for all $\fxx\in R_i\setminus\bigcup_m(\Gamma_{i,m}\cup\gamma_{i,m})$, or $u(\fxx)<\lambda$ for all $\fxx\in R_i\setminus\bigcup_m(\Gamma_{i,m}\cup\gamma_{i,m})$. Continuing this way, with arguments parallel to those given above, we arrive at expressions like \eqref{LSET} and \eqref{LSETT} for $\levelset_\lambda u_i$, where $u_i$ is the restriction of $u$ to $R_i$. Finally, $\levelset_\lambda u=\bigcup_i\levelset_\lambda u_i\cup\bigcup_j\Lambda_j$, where the $\Lambda_j$ are the $k$ Jordan arcs that terminate on the boundary of $R$. Of course, the sets $g_m$ in \eqref{LSETT} must be replaced with $g_{i,m}\cap R_i$.
\end{proof}

\begin{figure}[!t]
\setkeys{Gin}{width=10cm}
\centerline{
\includegraphics{fig04.02.1.eps}
}
\caption{\label{42} Level lines as representatives of the shapes present in an image.  Left: noisy binary image with two apparent shapes; right: the two longest level lines.}
\end{figure}

\section{Generalized level lines and topographic map}

We have made assumptions about the function $u$ so the level lines of $u$ are, for a dense set of $\lambda$, disjoint Jordan curves and arcs. This is nice for illustrating the ideas concerning the reconstruction of $u$ from its level lines, but it is too restrictive for practical digital processing. We wish to move to the situation where the level sets of $u$ are ``smooth enough'' so their boundaries are the unions of Jordan curves. Here is an example: Suppose $\Gamma$ is a Jordan curve and consider the function $u(\fxx)=1$ if $\fxx$ is inside $\Gamma$ and $u(\fxx)=0$ otherwise. The implicit function theorem does not apply, and the set $\{\fxx\mid u(\fxx)=1\}$ is not a level line. This leads to the following definition, which covers this particular case and others.

\begin{definition}Let $u$ be upper semicontinuous, which is equivalent to saying that its level sets are closed. Let $X$ be a level set of $u$ and consider the connected components of $X^c$, the complement of $X$. Assume that the boundary of each of these components is a finite union of Jordan curves that do not cross and that meet in at most a finite number of points. Under these conditions, we say that these Jordan curves are level lines of $u$.
\end{definition}

This definition may seem rather restrictive and it is. It has, however, the advantage of applying to one of the main situation in image processing and one we will be considering later in the book: upper semicontinuous piecewise constant images, in particular, images that are constant on the pixels. In this case, each level set is a union of closed squares on a grid, and it is easy to check that our definition applies and uniquely defines a set of Jordan curves that we call the level lines of the image. Conversely, these level lines uniquely define the associated level sets, and these level sets can be used to reconstruct the image.

As an example, consider a checkerboard image $u$, where the pixels have alternate values 255 (white) and 0 (black). If we decide that $u$ is u.s.c., then the white pixels include their boundaries and are connected. The black pixels are then disconnected. The level lines of $u$ are simply all the boundaries of the black pixels.


\begin{figure}[!t]
\setkeys{Gin}{width=3cm}
\centerline{
\includegraphics{fig04.03.1.eps}
}
\caption[Intrinsic coordinates]{\label{fig43}Intrinsic coordinates. Note that $\varphi''(0)>0$, so $b<0$.}
\end{figure}


\section{Curvature of the level lines}

We continue to work in $\RR^2$. Consider a real-valued function $u$ that is twice continuously differentiable in a neighborhood of $\fxx_0\in\RR^2$. Without loss of generality, we let $\fxx_0=0$ and assume that $u(0)=0$. (To simplify the notation, we will often write $Du$ rather than $Du(0)$, and so on.) If the gradient $Du=(u_x,u_y)\not=0$, then we establish a local coordinate system by letting $\bm{i}=Du/|Du|$ and $\bm{j}={Du}^{\perp}/|Du|$, where ${Du}^{\perp}=(-u_y,u_x)$. Thus, for a point $\fxx$ near $0$, we write $\fxx=x\bm{i}+y\bm{j}$. (See Figure \ref{fig43}.)

Since $u$ is $C^2$, we can use Taylor's formula to express $u$ in this coordinate system in a neighborhood of $0$:

\begin{equation}\label{57}
u(\fxx)=px+ax^2+by^2+cxy+O(|\fxx|^3),
\end{equation}
where $p=|Du(0)|>0$ and

\begin{equation}\label{58}
\begin{alignedat}{2}
a&=\frac{1}{2}\frac{\partial^2 u}{\partial x^2}(0)=&\frac1{2}D^2u\Big(\frac{Du}{|Du|},\frac{Du}{|Du|}\Big),\\
b&=\frac{1}{2}\frac{\partial^2 u}{\partial y^2}(0)=&\frac1{2}D^2u\Big(\frac{Du^{\perp}}{|Du|},\frac{Du^{\perp}}{|Du|}\Big),\\
c&=\frac{\partial^2 u}{\partial x\partial y}(0)=&D^2u\Big(\frac{Du^{\perp}}{|Du|},\frac{Du}{|Du|}\Big).
\end{alignedat}
\end{equation}

The implicit function theorem (Theorem 4.5) ensures that in a neighborhood of $0$, the set $\{\fxx\mid u(\fxx)=0\}$ is a $C^2$ graph whose equation can be written $x=\varphi(y)$, where $\varphi$ is a $C^2$ function in a neighborhood $N$ of $y=0$. In this neighborhood, we have $u(\varphi(y),y)=0$. Differentiating this shows that $u_x\varphi'+u_y=0$ for $y\in N$. Since $Du(0)=u_x(0)$ in the coordinate system defined in terms of $Du(0)/|Du(0)|$, we conclude that $u_y(0)=0$ and, hence, that $\varphi'(0)=0$. A second differentiation show that
\[
(u_{xx}\varphi'+u_{xy})\varphi'+ u_x\varphi''+u_{yx}\varphi'+u_{yy}=0.
\]
Since $\varphi'(0)=0$, we have $\varphi''(0)=-u_{yy}(0)/u_x(0)$. Then using the notation of \eqref{58}, we see that
\begin{equation}\label{59}
\varphi(y)=-\frac{b}{p}y^2+o(y^2).
\end{equation}

Equation \eqref{59} is the representation of the level line $\{\fxx\mid u(\fxx)=u(0)\}$ in the intrinsic coordinates at $0$. It is easy to show that $|2b/p|=1/R$ is the inverse of the radius of the circle that has ``three points of contact'' at $y=0$ with the curve $\{\varphi(y),y\}$. This circle is called the \textit{osculating circle}.

We are now going to do another simple computation to determine the curvature vector of the Jordan arc $\fxc$ defined by $\fxc(y)=(\varphi(y),y)$ near $y=0$. (From here on, we will generally denote the curvature of a curve $\fxc$ by ${\rm Curv}(\fxc)$ and the value of this function at a point $y$ by ${\rm Curv}(\fxc)(y)$.) Since $\fxc'(y)=(\varphi'(y),1)$ and $\fxc''(y)=(\varphi''(y),0)$, at $y=0$, we have  $\fxc'(0)=(0,1)$ and $\fxc''(0)=(\varphi''(0),0)$, so $\fxc''(0)\cdot\fxc'(0)=0$. Using this and equation \eqref{eq41} we see that ${\rm Curv}(\fxc)(0)=(\varphi''(0),0)$. We now use \eqref{59} and \eqref{58} to write the last expression as
\begin{equation}\label{eqcurv}
{\rm Curv}(\fxc)(0)=-\frac1{|Du|}D^2u\Big(\frac{Du^{\perp}}{|Du|},\frac{Du^{\perp}}{|Du|}\Big)\frac{Du}{|Du|}(0),
\end{equation}
 where all of the expressions are evaluated at $y=0$. This tells us that the vectors ${\rm Curv}(\fxc)(0)$ and $Du(0)$ are collinear. Equation \eqref{eqcurv} also leads to the following definition and lemma.

\begin{definition}Let $u$ be a real-valued function that is $C^2$ in a neighborhood of a point $\fxx\in\RR^2$ and assume that $Du(\fxx)\not=0$. The curvature of $u$ at $\fxx$, denoted by ${\rm curv}(u)(\fxx)$, is the real number defined by
\begin{equation}\label{curvu}
\frac{1}{|Du|^3}D^2u(Du^{\perp},Du^{\perp})(\fxx)=\frac{u_{xx}u_y^2-2u_{xy}u_xu_y+u_{yy}u_x^2}{(u_x^2+u_y^2)^{3/2}}(\fxx).
\end{equation}
\end{definition}

\begin{lemma}Assume that $u:\RR^2\to\RR$ is $C^2$ in a neighborhood of a point $\fxx_0$ and assume that $Du(\fxx_0)\not=0$. Let $N=N(\fxx_0)$ be a  neighborhood  of $\fxx_0$ in which the level set of $u$ $\{\fxx\mid u(\fxx)=u(\fxx_0)\}$ is a simple $C^2$ arc, which we denote by $\fxz$. Then
\begin{equation}\label{eq62x}
{\rm Curv}(\fxz)(\fxx)=-{\rm curv}(u)(\fxx)\frac{Du}{|Du|}(\fxx),
\end{equation}
where the relation holds for $\fxx\in N\cap\{\fxx\mid u(\fxx)=u(\fxx_0)\}$.
\end{lemma}

\begin{proof}We essentially proved the lemma when we derived equation \eqref{eqcurv} for $\fxx_0=0$. We need only remark that, given the hypotheses of the lemma, there is a neighborhood $N$ of $\fxx_0$ such that $Du(\fxx)\not=0$ for $\fxx\in N$ and such that $\{\fxx\mid u(\fxx)=u(\fxx_0)\}$ is a simple $C^2$ arc $\fxz$ for $\fxx\in N$. Then the argument we made to derive \eqref{eqcurv} holds for any point $\fxx\in N\cap\{\fxx\mid u(\fxx)=u(\fxx_0)\}$.
\end{proof}

\begin{exercise}Use equation \eqref{curvu} to show that
\begin{equation}
{\rm curv}(u)={\rm div}\Big(\frac{Du}{|Du|}\Big).
\end{equation}
Use this equation to show that ${\rm curv}(g(u))={\rm curv}(u)$ if $g$ is any $C^2$ function $g:\RR\to\RR$ such that $g'(x)>0$ for all $x\in\RR$. What happens if $g'(x)<0$ for all $x\in\RR$. Show that ${\rm curv}(U)={\rm curv}(u)$, where $U(s,t)=u(x,y)$ and $x=s\cos\theta-t\sin\theta$, $y=s\sin\theta+t\cos\theta$. \finex
\end{exercise}

\begin{exercise}The kinds of techniques used in this exercise are important for work in later chapters. The exercise demonstrates that it is possible to bracket a $C^2$ function locally with two functions that are radial and either increasing or decreasing.  We say that a function $f$ is radial and increasing if there exists an increasing function $g:\RR^+\to\RR$ such that $f(\fxx)=g(|\fxx_c-\fxx|^2)$, $\fxx_c\in\RR^2$. We say that $f$ is radial and decreasing if $g$ is decreasing. Let $u:\RR^2\to\RR$ be $C^2$ and assume that $Du(\fxx_0)\not=0$. We wish to show that for every $\varepsilon>0$ there exist two $C^2$ radial and functions $f^{-}_{\varepsilon}$ and $f^{+}_{\varepsilon}$ (increasing or decreasing, depending on the situation) that satisfy the following four conditions:
\begin{gather}
f^{-}_{\varepsilon}(\fxx_0)=u(\fxx_0)=f^{+}_{\varepsilon}(\fxx_0),\\
Df^{-}_{\varepsilon}(\fxx_0)=Du(\fxx_0)=Df^{+}_{\varepsilon}(\fxx_0),\\
{\rm curv}(f^{-}_{\varepsilon})(\fxx_0)+\frac{2\varepsilon}{p}={\rm curv}(u)(\fxx_0)={\rm curv}f^{+}_{\varepsilon}(\fxx_0)-\frac{2\varepsilon}{p},\\
f^{-}_{\varepsilon}(\fxx)+o(|\fxx_0-\fxx|^2)\leq u(\fxx)\leq f^{+}_{\varepsilon}(\fxx)+o(|\fxx_0-\fxx|^2).
\end{gather}

1. Without loss of generality, take $\fxx_0=(0,0)$, $u(0,0)=0$, and $Du(\fxx_0)=(p,0)$, $p>0$. Then we have the Taylor expansion
\[
u(\fxx)=px+ax^2+by^2+cxy+o(x^2+y^2),
\]
where $a$, $b$, and $c$ are given in \eqref{58}. Show that for every $\varepsilon>0$,
\[
px+\Big(-\frac{c^2}{\varepsilon}+a\Big)x^2+(b-\varepsilon)y^2+o(x^2+y^2)\leq u(x,y)\leq px+\Big(\frac{c^2}{\varepsilon}+a\Big)x^2+(b+\varepsilon)y^2+o(x^2+y^2).
\]

2. Let $f$ be a radial function defined by $f(x,y)=g((x-x_c)^2+y^2)$, where $g:\RR^+\to\RR$ is $C^2$ and either increasing or decreasing. Show by expanding $f$ at $(0,0)$ that
\[
f(x,y)=g(x_c^2)-2x_cg'(x_c^2)x+(2x_c^2g''(x_c^2)+g'(x_c^2))x^2+g'(x_c^2)y^2+o(x^2+y^2).
\]

3. The idea is to construct $f^{+}_{\varepsilon}$ and $f^{-}_{\varepsilon}$ by matching the coefficients of the expansion of $f$ with the coefficients of the functions $px+(\pm(c^2/{\varepsilon})+a)x^2+(b\pm\varepsilon)y^2$. There are three cases to consider: $b<0$, $b=0$, and $b>0$. Show that in each case it is possible to find values of $x_c$ and functions $g$ so the functions $f^{+}_{\varepsilon}$ and $f^{-}_{\varepsilon}$ satisfy the four condition. Note that both $x_c$ and $g$ depend on $\varepsilon$. Discuss the geometry for each case. \finex
\end{exercise}

Before leaving this section, we wish to emphasize geometric aspects of the functions we have introduced. Perhaps the most important fact is that the curvature of a $C^2$ Jordan arc $\Gamma$ is an intrinsic property of $\Gamma$; it does not depend on the parameterization. If $\fxx$ is a point on $\Gamma$, then the curvature vector ${\rm Curv}(\Gamma)(\fxx)$ points toward the center of the osculating circle, which is the circle that has three points of contact with $\Gamma$ at $\fxx$. Furthermore, $1/|{\rm Curv}(\Gamma)(\fxx)|$ is the radius of this circle, so when $|{\rm Curv}(\Gamma)(\fxx)|$ is large, the osculating circle is small, and the curve is "turning a sharp corner."

If $Du(\fxx)\not=0$, then the vector $Du(\fxx)$ points in the direction of greatest increase, or steepest ascent, of $u$ at $\fxx$: Following the gradient leads ``up hill.'' The function ${\rm curv}(u)$ does not have such a clear geometric interpretation, and it is perhaps best thought of in terms of equation \eqref{eq62x}: ${\rm curv}(u)(\fxx)$ is the coefficient of $-Du(\fxx)/|Du(\fxx)|$ that yields the curvature vector ${\rm Curv}(\fxz)(\fxx)$, where $\fxz$ is the level curve through the point $\fxx$ at level $u(\fxx)$. We cannot over emphasize the importance of the two operators curv and Curv for the theories that follow. In addition to \eqref{eq62x}, a further relation between these operators is shown in Proposition 5.8, and it is this result that connects function smoothing with curve smoothing.

\section{The principal curvatures of a level surface}

We saw in Exercise 4.5 that ${\rm curv}(u)$ was contrast invariant. This idea will be generalized to $\RR^N$ by introducing other differential operators that are contrast invariant. These operators will be functions of the \textit{principal curvatures} of the level surfaces of $u$. For $\fxz\in\RR^N$, $\fxz^\perp$ will denote the hyperplane $\{\fxy\mid \fxz\cdot\fxy=0\}$ that is orthogonal to $\fxz$. (There should be no confusion with this notation and the same notation for $\fxz\in\RR^2$. In $\RR^2$, $\fxz^\perp$ is a vector orthogonal to $\fxz$, and the corresponding ``hyperplane'' is the line $\{t\fxz^\perp\mid t\in\RR\}$.)

\begin{proposition}Assume that $u:\RR^N\to\RR$ is $C^2$ in a neighborhood of a point $\fxx_0$ and assume that $Du(\fxx_0)\not=0$. Let $g:\RR\to\RR$ be a $C^2$ contrast change such that $g'(s)>0$ for all $s\in\RR$.  Then $Dg(u(\fxx_0))=g'(u(\fxx_0))Du(\fxx_0)$, and $\tilde{D}^2g(u(\fxx_0))=g'(u(\fxx_0))\tilde{D}^2u(\fxx_0)$, where $\tilde{D}^2u(\fxx_0)$ denotes the restriction of the symmetric matrix $D^2u(\fxx_0)$  to the hyperplane $Du(\fxx_0)^\perp$. This means, in particular, that $(1/|Du(\fxx_0)|)\tilde{D}^2u(\fxx_0)$ is invariant under such a contrast change.
\end{proposition}

\begin{proof}To simplify the notation, we will suppress the argument $\fxx_0$; thus, we write $Du$ for $Du(\fxx_0)$, and so on. We use the notation $\fxy\otimes\fxy$, $\fxy\in\RR^N$, to denote the linear mapping $\fxy\otimes\fxy:\RR^N\to\RR^N$ defined by $(\fxy\otimes\fxy)(\fxx)=(\fxx\cdot\fxy)\fxy$. The range of $\fxy\otimes\fxy$ is the one-dimensional space $\RR\fxy$.

An application of the chain rule shows that $Dg(u)=g'(u)Du$. This implies that $Du^\perp=Dg(u)^\perp$. (Recall that $g'(s)>0$ for all $s\in\RR$.) A second differentiation shows that
\[
D^2g(u)=g''(u)Du\otimes Du+g'(u)D^2u.
\]
If $\fxy\in Du^\perp$, then $(Du\otimes Du)(\fxy)=0$, and we see that $D^2g(u)(\fxy,\fxy)=g'(u)D^2u(\fxy,\fxy)$. This means that $D^2g(u)=g'(u)D^2u$ on $Du^\perp=Dg(u)^\perp$, which proves the result.
\end{proof}

\begin{exercise}By computing explicitly the terms $\partial g(u)/\partial x_i$, verify that $Dg(u)=g'(u)Du$. Similarly, verify that $D^2(g(u))=g''(u)Du\otimes Du+g'(u)D^2u$ by computing the second-order terms $\partial^2 g(u) /\partial x_i\partial x_j$. \finex
\end{exercise}

We are now going to define locally the level surface of a smooth function $u$, and for this we quote one more version of the implicit function theorem.

\begin{theorem}[Implicit function theorem]Assume that $u:\RR^N\to\RR$ is $C^m$ in the neighborhood of $\fxx_0$ and assume that $Du(\fxx_0)\not=0$. Write $\fxx=\fxx_0+\fxy+z\bm{i}$, where $\bm{i}=Du(\fxx_0)/|Du(\fxx_0)|$ and  $\fxy\in Du(\fxx_0)^\perp$. Then there exists a ball $B(\fxx_0,\rho)$ and a unique real-valued $C^m$ function $\varphi$ defined on $B(\fxx_0,\rho)\cap\{\fxx\mid\fxx=\fxx_0+\fxy, \bm{i}\cdot\fxy=0\}$ such that for every $\fxx\in B(\fxx_0,\rho)$
\[
u(\fxx)=u(\fxx_0) \Longleftrightarrow \varphi(\fxy)=z.
\]
\end{theorem}

In other words, the equation $\varphi(\fxy)=z$ describes the set $\{\fxx\mid u(\fxx)=u(\fxx_0)\}$ near $\fxx_0$ as the graph of a $C^m$ function $\varphi$. Thus, locally we have a surface passing through $\fxx_0$ that we call the \textit{level surface of $u$ around $\fxx_0$}.

We are going to use Proposition 4.16 and Theorem 4.16, first, to give a simple intrinsic representation for the level surface of a function $u$ around a point $\fxx_0$ and, second, to relate the eigenvalues introduced in Proposition 4.16 to the curvatures of lines drawn on the level surface of $u$.

\begin{proposition}Assume that $u:\RR^N\to\RR$ is $C^2$ in a neighborhood of $\fxx_0\in\RR^N$ and that $p=Du(\fxx_0)\not=0$. Denote the eigenvalues of the restriction of the symmetric matrix $D^2u(\fxx_0)$ to the hyperplane $Du(\fxx_0)^\perp$ by $\kappa_1,\dots,\kappa_{N-1}$. Let $\bm{i}_N=Du(\fxx_0)/|Du(\fxx_0)|$ and select $\bm{i}_1,\ldots,\bm{i}_{N-1}$ so they form an orthonormal basis of eigenvectors of the restriction of $D^2u(\fxx_0)$ to  $Du(\fxx_0)^\perp$. Write $\fxx=\fxx_0+\fxz$, where $\fxz=x_1\bm{i}_1+\cdots+x_N\bm{i}_N=\fxy+x_N\bm{i}_N$. Then if $|\fxz|$ is sufficiently small, the function $\varphi(\fxy)=x_N$ that solves that equation $u(\fxy,\varphi(\fxy))=u(\fxx_0)$ can be expressed locally as
\[
x_N=\frac{-1}{2p}\sum_{i=1}^{N-1}\kappa_ix_i^2+o(|\fxy|^2).
\]
\end{proposition}

\begin{proof}Assume, without loss of generality, that $\fxx_0=0$ and that $u(0)=0$. Using the notation of Theorem 4.17, we know that, for $\fxx\in B(0,\rho)$, $u(\fxy,x_N)=0$ if and only if $\varphi(\fxy)=x_N$, and that $\varphi$ is $C^2$ in $B(0,\rho)$. Furthermore, by differentiating the expression $u(\fxy,\varphi(\fxy))=0$, we see that $u_{x_i}+u_{x_N}\varphi_{x_i}=0$, $i=1,\ldots,N-1$ for $|\fxx|<\rho$. In particular, $u_{x_i}(0)+u_{x_N}(0)\varphi_{x_i}(0)=0$. In the local coordinate system we have chosen, $|Du(0)|=|u_{x_N}(0)|$, and since $Du(0)\not=0$, we conclude that $u_{x_i}(0)=0$ for $i=1,\ldots,N-1$ and hence that $\varphi_{x_i}(0)=0$ for $i=1,\ldots,N-1$. This means that the local expansion of $\varphi$ has the form
\[
\varphi(\fxy)=\frac1{2}D^2\varphi(0)(\fxy,\fxy)+o(|\fxy|^2).
\]

Now differentiate the relation $u_{x_i}+u_{x_N}\varphi_{x_i}=0$ again to obtain
\[
u_{x_ix_j}+u_{x_ix_N}\varphi_{x_j}+(u_{x_Nx_j}+u_{x_Nx_N}\varphi_{x_j})\varphi_{x_i}+u_{x_N}\varphi_{x_ix_j}=0.
\]
Since we have just shown that $\varphi_{x_i}(0)=0$ for $i=1,\ldots,N-1$, we see from this last expression that $D^2u(0)+pD^2\varphi(0)=0$, where $p=u_{x_N}(0)$. Thus we have
\begin{equation}\label{513}
x_N=\frac{-1}{2p}D^2u(0)(\fxy,\fxy)+o(|\fxy|^2).
\end{equation}

Recall that $\fxy\in Du(0)^\perp$ and that $\fxy=x_1\bm{i}_1+\cdots+x_{N-1}\bm{i}_{N-1}$, where the $\bm{i}_i$ are an orthonormal basis of eigenvectors of $D^2(0)$ restricted to $Du(0)^\perp$. Thus,
\[
x_N=\frac{-1}{2p}\sum_{i=1}^{N-1}\kappa_ix_i^2+o(|\fxy|^2),
\]
which is what we wished to prove.
\end{proof}

This formula reads
\[
x_2=\frac{-1}{2p}\kappa_1x_1^2+o(|x_1|^2)
\]
if $N=2$, which is just equation \eqref{59} with different notation. Thus, $\kappa_1=|Du|{\rm curv}(u)$, confirming that $\kappa_1=\partial^2 u/\partial x_1^2$.

We are now going to use our two-dimensional analysis to give a further interpretation of the eigenvalues $\kappa_i$ for $N>2$. We begin by considering the curve $\Gamma_{\bm\nu}$ defined by the two equations
$\fxx=\fxx_0+t{\bm\nu}+x_N\bm{i}_N$ and $\varphi(t{\bm\nu})=x_N$, where ${\bm\nu}$ is a unit vector in $Du(\fxx_0)^\perp$. Their solution in the local coordinates is $\varphi(t\bm{\nu})=x_N$, whenever $t\in\RR$ is small. From the proof of Proposition 4.18, we know that
\[
\varphi(t\bm{\nu})=\frac{-1}{2|Du(\fxx_0)|}D^2u(\fxx_0)({\bm\nu},\bm{\nu})t^2+o(t^2),
\]
and a computation like the one we did to obtain equation \eqref{eqcurv} leads to the relation
\[
{\rm Curv}(\Gamma_{\bm\nu})(\fxx_0)=\frac{-1}{|Du(\fxx_0)|}D^2u(\fxx_0)({\bm\nu},{\bm\nu})\frac{Du(\fxx_0)}{|Du(\fxx_0)|}.
\]
By defining $\kappa_{\bm\nu}=|Du(\fxx_0)|^{-1}D^2u(\fxx_0)({\bm\nu},{\bm\nu})$, we have
\[
{\rm Curv}(\Gamma_{\bm{\bm\nu}})(\fxx_0)=-\kappa_{\bm\nu}\frac{Du(\fxx_0)}{|Du(\fxx_0)|},
\]
which has the same form as equation \eqref{eq62x}. This suggest calling $\kappa_{\bm\nu}$ a curvature, and we will do this but only in case ${\bm\nu}$ is one of the eigenvectors of $D^2u(\fxx_0)$ restricted to $Du^\perp$.

\begin{definition}The principal curvatures of the level surface of $u$ at $\fxx_0$ are by definition the numbers $\kappa_{\bm{\nu}}$ obtained by letting $\bm{\nu}=\bm{i}_j$, $j=1,\ldots,N-1$, where the unit vectors $\bm{i}_j$ are the eigenvectors of $D^2u(\fxx_0)$ restricted to $Du(\fxx_0)^\perp$.
\end{definition}

Thus, the principal curvatures of $u$ at $\fxx_0$ are the real numbers
\[
\kappa_{\bm{i}_j}=\frac{\kappa_j}{|Du(\fxx_0)|},
\]
where the $\kappa_j$ are the eigenvalues of $D^2u(\fxx_0)$ restricted to $Du(\fxx_0)^\perp$. It follows from Proposition 4.16 that the principal curvatures are invariant under a $C^2$ contrast change $g$ such that $g'(s)>0$ for all $s\in\RR$.

\begin{definition}The mean curvature of a $C^2$ function $u:\RR^N\to\RR$ at $\fxx_0\in\RR^N$ is the sum of the principal curvatures at $\fxx_0$. It is denoted by ${\rm curv}(u)(\fxx_0)$.
\end{definition}

Note that this definition agrees with the Definition 4.14 when $N=2$. The next result provides another representation for ${\rm curv}(u)$.

\begin{proposition}The mean curvature of $u$ is given by
\[
{\rm curv}(u)={\rm div}\Big(\frac{Du}{|Du|}\Big).
\]
\end{proposition}
\begin{proof}Represent the matrix $D^2u$ in the coordinate system $\bm{i}_j$, $j=1,\ldots,N-1$, and $\bm{i}_N=Du(\fxx_0)/|Du(\fxx_0)|$, where the $\bm{i}_j$, $j=1,\ldots,N-1$, form a complete set of eigenvectors of the linear mapping $D^2u(\fxx_0)$ restricted to $Du^\perp(\fxx_0)$. Then in this coordinates system, $D^2u(\fxx_0)$ has the following form (illustrated for $N=5$):
\begin{equation*}D^2u(\fxx_0)=
\begin{bmatrix}
u_{11}&0&0&0&u_{15}\\
0&u_{22}&0&0&u_{25}\\
0&0&u_{33}&0&u_{35}\\
0&0&0&u_{44}&u_{45}\\
u_{51}&u_{52}&u_{53}&u_{54}&u_{55}
\end{bmatrix},
\end{equation*}
where $u_{jk}=u_{x_jx_k}(\fxx_0)$, and $u_{jj}=\kappa_j$ is the eigenvalue associated with $\bm{i}_j$. Thus, by definition, we see that
\[
{\rm curv}(u)=\frac{\Delta u}{|Du|}-\frac1{|Du|}D^2u\Big(\frac{Du}{|Du|},\frac{Du}{|Du|}\Big).
\]
We also have
\begin{align*}
{\rm div}\Big(\frac{Du}{|Du|}\Big)&=\sum_{j=1}^N \frac{\partial}{\partial x_j}\Big(\frac{u_{x_j}}{|Du|}\Big)\\
&=\frac1{|Du|}\sum_{j=1}^N u_{x_jx_j}-\frac1{|Du|^3}\sum_{j,k=1}^N u_{x_jx_k}u_{x_j}u_{x_k}\\
&=\frac{\Delta u}{|Du|}-\frac1{|Du|}D^2u\Big(\frac{Du}{|Du|},\frac{Du}{|Du|}\Big).\qedhere
\end{align*}
\end{proof}

With this representation, it is clear that the mean curvature has the same invariant properties as the curvature of a $C^2$ function defined on $\RR^2$. (See Exercise 4.5.)

\section{Comments and references}

\paragraph*{Calculus and differential geometry.} The differential calculus of curves and surfaces used in this chapter can be found in many books, and no doubt most readers are familiar with this material. Nevertheless, a few references to specific results may be useful. As a general reference on calculus, and as a specific reference for the implicit function theorem, we suggest the text by Courant and John \cite{CJ2000}. (The implicit function theorem can be found on page 221 of volume II.) Elementary results about classical differential geometry can be found in \cite{DS1950}. A statement and proof of Sard's theorem can be found in \cite{KP1999}.

\paragraph*{Topology of plane sets.} All of the material presented is quite straightforward, except the Jordan curve theorem. We believe that one of the best proofs of this result is still to be found in the book by M. H. A. Newman \cite{MHAN1951}. Newman's treatment is elementary, it describes the problems associated with proving this ``obvious'' result, and it introduces the nonspecialist to some simple combinatorial topology. Another interesting approach to prove the Jordan curve theorem can be found in \cite{JD1960}.

\paragraph*{Level lines.} An introduction to the use of level lines in computer vision can be found in \cite{Caselles:1999:TML}. We relied directly on the Jordan curve theorem to show that the level sets of a function, and hence the function, could be reconstructed from its level lines (Propositions 4.11 and 4.12). In Proposition 4.12 we made some (unnecessary) assumptions to ensure that we were dealing with a finite number of curves in the rectangle. A more general reconstruction assumes that the set to be reconstructed from its boundary is a set with finite perimeter. Then it can be shown that the set's boundary can be defined uniquely as a countable union of Jordan arcs and curves, and the reconstruction is still valid. A complete discussion of this general reconstruction is given in \cite{AMCAMAMO}.

\paragraph*{Curvature.} It is by now a well-known mathematical technique to define a set implicitly as the zero set of its distance function. In case the set is a curve, one can compute its curvature at a point $\fxx$ by computing the curvature ${\rm curv}(u)(\fxx)$, where $u$ is a signed distance function of the curve. This yields an intrinsic formula for the curvature that is not dependent on a parameterization of the curve. The same technique has been applied in recent years as a useful numerical tool. This started with Barles report on flame propagation and was extended by Sethian \cite{Sethian:1982:AFP} and by Osher and Sethian \cite{Osher:1988:FPCb} in a series of papers on the numerical simulation of the motion of a surface by its mean curvature.

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