%gmIntro.tex

\graphicspath{{./figures/}}


\addcontentsline{toc}{chapter}{Introduction}
\markboth{Introduction}{Introduction}

\renewcommand{\thesection}{{I}.\arabic{section}}
\renewcommand{\thefigure}{{I}.\arabic{figure}}
\renewcommand{\theequation}{{I}.\arabic{equation}}



\begin{figure}[!ht]
\setkeys{Gin}{width=10cm}
\centerline{
\includegraphics{fig00.01.0.eps}
}
\caption[A noisy image]{\label{biga} A noisy image magnified to show the pixels.}
\end{figure}
 \begin{slide}

{\em Digital image : first the underlying image $u_S$, then a
smoothed by optics version $u_f$, finally the  digital one $u_d$,
discrete on a grid. It is widely assumed that the underlying
``real image'' $u_S$ is either a measure or, for more optimistic
authors, a function that has strong discontinuities. Rudin in 1987
and De~Giorgi and Ambrosio in 1988 proposed independently the
space $BV(\mathbb R^2)$ of functions with bounded variation as the
correct function space for modeling the images $u_S$.
\newline
\newline A function $f$ is in $BV(\mathbb R^2)$ if its partial
derivatives ${\partial f}/{\partial x}$ and ${\partial
f}/{\partial y}$, taken as distributions, are Radon measures with
finite total mass. $BV(\mathbb R^2)$ looked at first well adapted
to modelling digital images because it contains functions having
step discontinuities.}

\end{slide}
\section{Image processing}
Three disciplines with different scopes and different techniques :
compression, restoration, analysis.
\begin{figure}[!ht]
\setkeys{Gin}{width=3cm}
\centerline{
\includegraphics{fig00.01.1.eps}
\includegraphics{fig00.01.2.eps}
\includegraphics{fig00.01.3.eps}
\includegraphics{fig00.01.4.eps}
}
\caption[Compression]{\label{IMGPREFACE1} Compression. Left to right: the original image and its increasingly compressed versions. The compression factors are roughly 7, 10, and 25.}
\end{figure}

\begin{figure}[!ht]
\setkeys{Gin}{width=3cm}
\centerline{
\includegraphics{fig00.02.1.eps}
\includegraphics{fig00.02.2.eps}
}
\caption[Denoising]{\label{IMGPREFACE2} Denoising. Left: an image with up to 75\% of its pixels contaminated by simulated noise. Right: a denoised version.}
\end{figure}



\begin{figure}[!ht]
\setkeys{Gin}{width=3cm}
\centerline{
\includegraphics{fig00.03.1.eps}
\includegraphics{fig00.03.2.eps}
\includegraphics{fig00.03.3.eps}
\includegraphics{fig00.03.4.eps}
}
\caption[Analysis of a shape]{\label{IMGPREFACE3} Analysis of a shape. The original scanned shape is on the left. Simplified versions are to the right.  }
\end{figure}

 \begin{slide}

\section{PDEs and image processing}
\begin{figure}[!ht]
\setkeys{Gin}{width=3cm}
\centerline{
\includegraphics{fig00.05.1.eps}
\includegraphics{fig00.05.2.eps}
}
\caption[Heat equation and smoothing]{\label{IMGPREFACE5} Heat equation and smoothing. The original image is on the left; the heat equation has been applied at some scale, and the resulting blurred image is on the right.}
\end{figure}

\end{slide}\begin{slide}
  $k$ is
any positive kernel such that $k(\bm{x})=k(|\bm{x}|)$ and such
that $k$ is localized in the sense that $k(\bm{x})\to 0$
sufficiently rapidly as $|\bm{x}|\to\infty$. If $k$ is normalized
properly and if   $k_h(\fxx)=(1/h)k({\fxx}/{h^{1/2}})$, then
\[
\frac {k_h\ast u_0(\fxx)  -u_0(\fxx)}h  \to\Delta u_0(\fxx)
\]
as $h\to 0$ whenever the image $u_0$ is sufficiently smooth. We write this as
\begin{equation}\label{r1}
k_h\ast u_0(\fxx)  -u_0(\fxx)=h\Delta u_0(\fxx)+o(h).
\end{equation}
Now let $u(t,\bm{x})$ denote the solution of the heat equation
\[
\frac{\partial u}{\partial t}=\Delta u, \quad u(0,\bm{x})=u_0(\bm{x}).
\]
If $u_0$ is sufficiently smooth, then we can write
\begin{equation}\label{r2}
u(t,\bm{x})-u(0,\bm{x})=t\Delta u_0(\fxx)+o(t).
\end{equation}
\end{slide}\begin{slide}
Equations \eqref{r1} and \eqref{r2} suggest that blurring $u_0$
with a kernel $k_h$ for small $h$ is equivalent to applying the
heat equation to $u_0$ at some small scale $t$. Lindenbaum,
Fischer, and Bruckstein that Kovasznay and Joseph
 introduced in 1955 the notion that a
slightly blurred image could be deblurred by subtracting a small
amount of its Laplacian. Numerically, this amounts to subtracting
a fraction $\lambda$ of the Laplacian of the observed image from
itself (later, Dennis Gabor found the optimal parameter for the
method):
\[
u_{\mathrm{restored}}=u_{\mathrm{observed}}- \lambda\Delta u_{\mathrm{observed}}.
\]
\end{slide}\begin{slide}
\begin{figure}[!ht]
\setkeys{Gin}{width=3cm}
\centerline{
\includegraphics{fig00.06.1.eps}
\includegraphics{fig00.06.2.eps}
\includegraphics{fig00.06.3.eps}
}
\caption[Kovasznay--Joseph--Gabor deblurring I]{\label{IMGPREFACE6} Kovasznay--Joseph--Gabor deblurring. Left to right: original image; three iterations of the algorithm; ten iterations of the algorithm.\label{vicdeblur}}
\end{figure}
\end{slide}\begin{slide}

\begin{figure}[!ht]
\setkeys{Gin}{width=3cm}
\centerline{
\includegraphics{fig00.07.1.eps}
\includegraphics{fig00.07.2.eps}
\includegraphics{fig00.07.3.eps}
}
\caption[Kovasznay--Joseph--Gabor deblurring II]{\label{IMGPREFACE7} Kovasznay--Joseph--Gabor deblurring. This is the same deblurring experiment as in Figure \ref{vicdeblur}, but it is applied to a much more blurred image.}
\end{figure}
\end{slide}\begin{slide}
  Rudin in 1987  and Osher and Rudin in
1990 proposed  a pseudoinverse for the heat equation, where the
propagation term $|Du|=|(u_x, u_y)|$ is controlled by the sign of
the Laplacian:
\begin{equation}\label{ro}
\frac {\partial u}{\partial t} = -\mathrm{sign}(\Delta u) |Du|.
\end{equation}
A {\it shock filter}, propagates the level lines of an image with
a constant speed and in the same direction as the reverse heat
equation would propagate these lines : pseudoinverse for the heat
equation.

\end{slide}\begin{slide} An improvement (Guichard et al.),
 Kramer's filter  (seventies) not formulated as a PDE, but equivalent to
 a shock filter :
\begin{equation}\label{kramer}
\frac {\partial u}{\partial t} = -\mathrm{sign}(D^2u(Du, Du)) |Du|,
\end{equation}
where the Laplacian has been replaced by
\[
D^2u(Du, Du)=u_{xx}(u_x)^2+2u_{xy}u_xu_y+u_{yy}(u_y)^2.
\]

 $D^2u(Du, Du)/|Du|^2$ is the second
derivative of $u$ in the direction of its gradient $Du$,
Haralick's edge detector. Kramer's equation yields a slightly
better version of a shock filter.

\end{slide}\begin{slide}
A third deblurring method, the Rudin--Osher--Fatemi algorithm, is
definitely better. It poses the deblurring problem as an inverse
problem.   Given the observed image $u_0$, one tries to find a
restored version $u$ such that $k\ast u$ is as close as possible
to $u_0$ and such that the oscillation of $u$ is nonetheless
bounded. This is done by finding $u$ that minimizes
\begin{equation}\label{rof}
\int \big(|Du(\bm{x})| + \lambda (k\ast u(\bm{x})
-u_0(\bm{x}))^2\big)\,\rmd\fxx.
\end{equation}

\end{slide}
\begin{figure}[!ht]
\setkeys{Gin}{width=3cm}
\centerline{
\includegraphics{fig00.08.1.eps}
\includegraphics{fig00.08.2.eps}
\includegraphics{fig00.08.3.eps}
\includegraphics{fig00.08.4.eps}
}
\caption[Deblurring with shock filters and a variational method]{
\label{IMGPREFACE10}
Deblurring with shock filters and a variational method.  Left to right: blurred image; Rudin--Osher shock filter; Kramer's improved shock filter; Rudin--Osher--Fatemi restoration method.}
\end{figure}
 \begin{slide}
In 1983, Burt and Adelson  : Laplacian pyramid.  A convolution
followed by subsampling. After each convolution, one keeps only
the difference $k_n*u_n-u_n \simeq \Delta u_n$  The image is then
coded by the (finite) sequence of these differences which tend to
be sparse for natural images.
\end{slide}
\begin{figure}[!ht]
\setkeys{Gin}{width=3cm}
\centerline{
\includegraphics{fig00.09.1.eps}
\includegraphics{fig00.09.2.eps}
\includegraphics{fig00.09.3.eps}
\includegraphics{fig00.09.4.eps}
}
\caption[The Laplacian pyramid]{\label{IMGPREFACE8} The Laplacian pyramid of Burt and Adelson. Left to right: the original image; the image blurred by Gaussian convolution; the difference between the original image and the blurred version, which approximates the Laplacian of the original image; the points where this Laplacian image is large.}
\end{figure}
 \begin{slide}
 {\Large Edge detection}
 \newline
  Marr and Hildreth proposed
computing the points where $\Delta u$ crosses zero, the now-famous
zero-crossings. A significant improvement was made by Haralick who
defined the boundaries, or edges, of an image as those points
where $|Du|$ attains a local maximum along the gradient lines
  Canny implemented Haralick's
detector   Gaussian smoothing followed by computing the (edge)
points where $D^2u(Du, Du)=0$ and $|Du|$ is above some threshold

\end{slide}

\begin{figure}[!ht]
\setkeys{Gin}{width=6cm}
\centerline{
\includegraphics{fig00.10.1.eps}
\includegraphics{fig00.10.2.eps}
}
\caption[\label{heatequationandCanny}Heat equation and Haralick's edge detector]{\label{IMGPREFACE9}
Heat equation and Haralick's edge detector.  Left to right: original image; edge points found in the original image using Haralick's detector; blurred image; edges found in the blurred image using the Haralick--Canny detector.}
\end{figure}
 \begin{slide}
  Perona and Malik  :
to smooth what needs to be smoothed, namely, the irrelevant
homogeneous regions, and to enhance the boundaries. With this in
mind, the diffusion should look like the heat equation when $|Du|$
is small, but it should act like the inverse heat equation when
$|Du|$ is large.
\begin{equation}\label{PM}
\frac {\partial u}{\partial t} = \mathrm{div}(g(|Du|)Du),
\end{equation}
where $g(s) = 1/(1+\lambda^2 s^2)$. It is easily checked that we
have a diffusion equation when $\lambda|Du|\leq1$ and an inverse
diffusion equation when $\lambda|Du|>1$.
\end{slide}\begin{slide}

 To see this, consider the
second derivative of $u$ in the direction of $Du$,
\[
u_{\xi\xi}= D^2u\bigg(\frac {Du}{|Du|}, \frac {Du}{|Du|}\bigg),
\]
and the second derivative of $u$ in the orthogonal direction,
\[
u_{\eta\eta}= D^2u\bigg(\frac {Du^\perp}{|Du|}, \frac {Du^\perp}{|Du|}\bigg),
\]
where $Du=(u_x, u_y)$ and $Du^\perp = (-u_y, u_x)$.  The Laplacian can be  rewritten in the intrinsic coordinates $(\xi, \eta)$ as
$\Delta u = u_{\xi\xi}+u_{\eta\eta}$. The Perona--Malik equation then becomes
\[
\frac {\partial u}{\partial t} = \frac{1}{1+\lambda^2|Du|^2}u_{\eta\eta}
+\frac{1-\lambda^2|Du|^2}{(1+\lambda^2|Du|^2)^2}u_{\xi\xi}.
\]
 This model   mixes the heat equation and the reverse
heat equation.
\end{slide}
\begin{figure}[!ht]
\setkeys{Gin}{width=6cm}
\centerline{
\includegraphics{fig00.11.1.eps}
\includegraphics{fig00.11.2.eps}
} \caption[A Perona and Malik equation and edge
detection]{\label{IMGPREFACE11} A Perona--Malik equation and edge
detection. This is the same experiment as in Figure I.11, but here
the Perona--Malik equation is used in place of the heat equation.
Notice that the edge map looks slightly better in this case.}
\end{figure}

 \begin{slide}

 {\Large A proliferation of anisotropic diffusions...}
 \newline
  Rudin--Osher--Fatemi model  $\int |Du(\bm{x})|\,{\rm
d}\bm{x}$, which is the $BV$ norm of $u$. The gradient descent for
$\int |Du(\bm{x})|\,{\rm d}\bm{x}$ translates into the equation
\[
\frac {\partial u}{\partial t} = \mathrm{div} \bigg(\frac {Du}{|Du|}\bigg)=\frac 1 {|Du|} u_{\eta\eta}.
\]
Written this way, the method appears as diffusion in the direction
orthogonal to the gradient, tuned by the size of the gradient.
Andreu, Caselles and Mazon proved that this equation is well
posed.

Alvarez, Lions, et al. :
\[
\frac {\partial u}{\partial t} =\frac {1}{|k\ast Du|}\,|Du|\, \mathrm{div}\bigg (\frac {Du}{|Du|}\bigg)=\frac 1 {|k\ast Du|} u_{\eta\eta},
\]
and again the diffusion is in the direction $Du^\perp$ orthogonal
to the gradient. Note that the rate of diffusion depends on the
average value $k\ast Du$ of the gradient in a neighborhood of
$\bm{x}$, whereas the direction of diffusion,
$Du^\perp(\bm{x})/|Du(\bm{x})|$, depends on the value of
$Du(\bm{x})$ at $\bm{x}$.

Kimia, Tannenbaum, and Zucker,   in a more general shape-analysis
framework taken from Osher-Sethian:
\begin{equation}\label{curveqn}
\frac {\partial u}{\partial t} =|Du|\;\mathrm{div}\bigg (\frac {Du}{|Du|}\bigg)= D^2u\bigg(\frac {Du^\perp}{|Du|}, \frac {Du^\perp}{|Du|}\bigg)=u_{\eta\eta}.
\end{equation}
 This equation is a ``pure" diffusion in
the direction orthogonal to the gradient. We call this equation
{\it the curvature equation}.

The Weickert equation

$$\frac {\partial u}{\partial t} =  D^2u\bigg( v_1^\perp, v_1^\perp\bigg)=u_{{v_1v_1}}
$$
  uses a nonlocal estimate of the direction
orthogonal to the gradient for the diffusion direction.The
eigenvector corresponding to the smallest eigenvalue of
$k\ast(Du\otimes Du)$, where
$(\bm{y}\otimes\bm{y})(\bm{x})=(\bm{x}\cdot\bm{y})\bm{y}$. If the
convolution kernel is removed, then this eigenvector is simply
$Du^\perp$.
\end{slide}\begin{slide}

Carmona and Zhong proposed a diffusion in the direction of the
eigenvector corresponding to the smallest eigenvalue of $D^2u$
  Sochen, Kimmel, and Malladi proposed
  a nondegenerate diffusion associated with a minimal
surface variational formulation \cite{Sochen:1998:GFL}. Their idea
was to make a gradient descent for the area, $\int
\sqrt{1+|Du(\bm{x})|^2}\,{\mathrm d}\bm{x}$, of the graph of $u$.
This leads to the diffusion equation
\[
\frac {\partial u}{\partial t} = \mathrm{div}\bigg (\frac {Du}{\sqrt{1+|Du|^2}}\bigg).
\]

\end{slide}\begin{slide}
  Caselles, Morel, and Sbert proposed a diffusion to interpolate
  between level lines
\[
\frac {\partial u}{\partial t} = D^2u(Du, Du)=|Du|^2u_{\xi\xi}.
\]
  Among the models mentioned, only the
curvature motion proposed by Kimia, Tannenbaum, and Zucker was
specifically introduced as a shape analysis tool.
\end{slide}
\begin{figure}[!ht]
\setkeys{Gin}{width=3cm} \centerline{
\includegraphics{fig00.14.1.eps}
\includegraphics{fig00.14.2.eps}
\includegraphics{fig00.14.3.eps}
\includegraphics{fig00.14.4.eps}
}
\caption[Diffusion models I]{\label{IMGPREFACE13} Diffusion models I. Left to right: Osher, Sethian 1988: the curvature equation; Rudin, Osher, Fatemi 1992: minimization of the image's total variation; Alvarez, Lions, Morel 1992: nonlocal variant of the preceding; Weickert 1994: nonlocal variant of the curvature equation.  All of these models diffuse only in the direction orthogonal to the gradient, using a more or less local estimate of this direction.}
\end{figure}

\begin{figure}[!ht]
\setkeys{Gin}{width=3cm}
\centerline{
\includegraphics{fig00.12.1.eps}
\includegraphics{fig00.12.2.eps}
\includegraphics{fig00.12.3.eps}
\includegraphics{fig00.12.4.eps}
}
\caption[Diffusion models II]{\label{IMGPREFACE12} Diffusion models II. Left to right: original image; Perona--Malik equation 1987; Carmona, Zhong 1998: diffusion along the least eigenvector of $D^2u$; Sochen, Kimmel, Malladi 1998: minimization of the image graph area.}
\end{figure}

\begin{figure}[!ht]
\setkeys{Gin}{width=3cm}
\centerline{
\includegraphics{fig00.13.1.eps}
\includegraphics{fig00.13.2.eps}
\includegraphics{fig00.13.3.eps}
}
\caption[Diffusion models III]{\label{IMGPREFACE14} Diffusion models III.  Left to right: original image; quantized image (only 10 levels are kept - 3.32 bits/pixel); the quantized image reinterpolated using the Caselles--Sbert algorithm 1998. They apply a diffusion on the quantized image with values on the remaining level lines as boundary conditions.}
\end{figure}


 \begin{slide}
 \vspace{-8pt} \subparagraph{\large Contrast-invariant
classes.}Two images $u$ and $v$ are said to be (perceptually)
equivalent if there is a continuous increasing function $g$ such
that $v=g(u)$. In this case, $u$ and $v$ are said to belong to the
same contrast-invariant class. (``Increasing'' always means
``strictly increasing.'')
\end{slide}\begin{slide}
\vspace{-8pt} \subparagraph{Contrast invariance requirement.}An
image analysis operator $T$ must act directly on the equivalence
class. As a consequence, we ask that $T(g(u))=g(Tu)$, which means
that the image analysis operator commutes with contrast changes.
(Note that contrast changes $g$ are not limited to increasing
functions.)
\end{slide}\begin{slide}
\medskip
  Matheron in 1975
formulates image analysis as set analysis, namely, the analysis of
the level sets of an image. The {\it upper level set} of an image
$u$ at level $\lambda$ is the set
\[
\levelset_\lambda u= \{\fxx\mid u(\fxx)\geq \lambda\}.
\]
We define in exactly the same way the {\it lower level sets} by
changing ``$ \geq$'' into ``$\leq$.''  The main point to retain
here is the global invariance of level sets under contrast
changes. Thus, if $g$ is a continuous increasing contrast change,
then
\[
\levelset_{g(\lambda)}g(u)=\levelset_\lambda u.
\]
\end{slide}\begin{slide}
According to mathematical morphology,   all of an image's shape
information is contained in its level sets (forgetting about their
levels).
\end{slide}\begin{slide}
\begin{figure}[!ht]
\setkeys{Gin}{width=3cm}
\centerline{
\includegraphics{fig00.15.1.eps}
\includegraphics{fig00.15.2.eps}
}
\caption[level set of an image]{\label{IMGPREFACE16} An image and one of its level sets. On the right is level set 140 of the left image. This experiment illustrates Matheron's thesis that the main shape information is contained in the level sets of an image. Level sets are contrast invariant.}
\end{figure}
\end{slide}\begin{slide}
  {\Large Extrema killer (Guichard), grain filter (Guichard-Monasse), area filter (Vincent) }
defined by Vincent in 1993  This image operator simply removes all
connected components of upper and lower level sets with areas
smaller than some fixed value in the first and third definition.
More cleverly, it removes all level lines who surround an area
less than some threshold in the middle definition.
\end{slide}
\begin{figure}[!ht]
\setkeys{Gin}{width=3cm}
\centerline{
\includegraphics{fig00.16.1.eps}
\includegraphics{fig00.16.2.eps}
\includegraphics{fig00.16.3.eps}
\includegraphics{fig00.16.4.eps}
}
\caption[Extrema killer]{\label{IMGPREFACE15} The extrema killer filter. Left to right: original image; extrema killer applied with area threshold equal 80 pixels; 75\% salt and pepper noise added to the original image; the same filter applied.}
\end{figure}
 \begin{slide}

In 1996, Caselles, Coll et al.   proposed as the main objects of
analysis the {\it level lines} of an image, that is, the
boundaries of its level sets. Level sets and isolevel sets
$\{\fxx\mid u(\fxx)=\lambda\}$, computed for  an interpolation of
the  digital image.

 For an interpolation method to be
useful, the level lines should have certain minimal properties:
They should be composed of a finite number of rectifiable Jordan
curves, and they should be nested. This means that they do not
cross, and thus that they form a tree by inclusion.

Kronrod  1950 shows that if the function $u$ is continuous, then
the isolevels sets $\{\fxx\mid u(\fxx)=\lambda\}$ are nested and
thus form a tree when ordered by inclusion. These isolevel sets
are not necessarily curves; they are curves, however, if $u$ has
continuous first derivatives. Monasse proved Kronrod's result for
lower semicontinuous and upper semicontinuous functions in 2000.
\end{slide}
\begin{slide}
\begin{figure}[!ht]
\setkeys{Gin}{width=3cm}
\centerline{
\includegraphics{fig00.17.1.eps}
\includegraphics{fig00.17.2.eps}
}
\caption[Level lines of an image]{\label{IMGPREFACE17} Level lines of an image. Level lines, defined as the boundaries of level sets, can be defined to be a nested set of Jordan curves. They provide a contrast-invariant representation of the image. On the right are the level lines at level 183 of the left image.}
\end{figure}
\end{slide}

\begin{slide}  Lecture notes on Image iterative filtering and P.D.E.'s
 by F. Guichard, J.M.M. and Bob Ryan
to be downloaded chapter by chapter at :

\medskip \noindent
http://www.cmla.ens-cachan.fr/Utilisateurs/morel/GMRChap01.pdf\newline
http://www.cmla.ens-cachan.fr/Utilisateurs/morel/GMRChap02.pdf\newline
........
\newline
....... \newline
http://www.cmla.ens-cachan.fr/Utilisateurs/morel/GMRChap19.pdf\newline
http://www.cmla.ens-cachan.fr/Utilisateurs/morel/GMRIntro.pdf\newline
http://www.cmla.ens-cachan.fr/Utilisateurs/morel/GMRBib.pdf\newline
http://www.cmla.ens-cachan.fr/Utilisateurs/morel/GMRApndxA.pdf\newline
\end{slide}
\begin{slide}
Many (and the most important) mentioned image processing methods
are accessible in the software
\texttt{http://www.cmla.ens-cachan.fr}.

\end{slide}


\begin{slide}
Chen, Giga, and Goto   and Alvarez et al. proved that if one adds
contrast invariance to the  usual isotropic invariance  then all
multiscale image analyses should have a curvature-dependent motion
of the form
\begin{equation}\label{curve}
 \frac {\partial u}{\partial t} = F(\mathrm{curv}(u), t) |Du|,
\end{equation}
where $F$ is increasing with respect to its first argument. This
equation can be interpreted as follows: Consider a point $\fxx$ on
a given level curve $C$ of $u$ at time $t$. Let $n(\fxx)$ denote
the unit vector normal to $C$ at $\fxx$ and let
$\mathrm{curv}(\fxx)$ denote its curvature. Then the preceding
equation is associated with the curve motion equation
\[
\frac {\partial \fxx}{\partial t} = F(\mathrm{curv}(\fxx), t) n(\fxx)
\]
that describes how the point $\fxx$ moves in the direction of the
normal.

\end{slide}\begin{slide} Two main examples :
\newline
 $F(\mathrm{curv}(u),
t)=\mathrm{curv}(u)$, the curvature equation.
\newline
$F(\mathrm{curv}(u), t) = (\mathrm{curv}(u))^{1/3}$, the affine
morphological scale space (AMSS)

This particular one-third power form for the curvature dependence
provides an important additional invariance, namely, affine
invariance. We would like to have complete projective invariance,
but a theorem proved by Alvarez et al. shows that this is
impossible. The best we can have is invariance with respect to the
so-called Chinese perspective, which preserves parallelism. Most
of these equations, particularly when $F$ is a power of the
curvature, have a viscosity solution in the sense of Crandall and
Lions. This was shown in 1995 by Ishii and Souganidis.
\end{slide}\begin{slide}
As we have mentioned, contrast-invariant processing can be reduced
to level set processing and, finally, to level curve processing.
The equations mentioned above are indeed equivalent to curve
evolution models if existence and regularity have been
established. These results exist for the most important cases,
namely, for $F(\mathrm{curv}(u), t)=\mathrm{curv}(u)$, called {\it
curve shortening}, and for $F(\mathrm{curv}(u), t) =
(\mathrm{curv}(u))^{1/3}$, known as {\it affine  curve shortening
(Sapiro and Tannenbaum)}. Grayson proved existence, uniqueness,
and analyticity for the curve shortening equation,
\begin{equation}\label{curveshort}
\frac {\partial \fxx}{\partial t} =\mathrm{curv}(\fxx)n(\fxx),
\end{equation}
and Angenent, Sapiro, and Tannenbaum proved the same results for the affine shortening equation \cite{Angenent:1998:AHF},
\begin{equation}\label{affineshort}
\frac {\partial \fxx}{\partial t} = (\mathrm{curv}(\fxx))^\frac13 n (\fxx).
\end{equation}
These results are very important for image analysis : why ?
\end{slide}

\begin{figure}[!ht]
\setkeys{Gin}{width=4.2cm}
\centerline{
\includegraphics{fig00.19.1.eps}
\includegraphics{fig00.19.2.eps}
\includegraphics{fig00.19.3.eps}
} \caption[Experimental verification of the  affine invariance of
the affine shortening (AMSS)]{\label{IMGPREFACE21} Experimental
verification of the affine invariance of the affine shortening
(AMSS). The first panel contains three shapes, $X$, $A(X)$, and
$A^{-1}A(X)$. The second panel contains $S(X)$, $SA(X)$, and
$A^{-1}SA(X)$. The congruence of the first and third shapes
implies that $S$ and $A$ commute. In the third panel, the same
procedure has been applied using the curvature equation. Here the
first and third shapes are not congruent, which shows that the
curve shortening is not affine invariant, as expected.}
\end{figure}
\begin{slide}
Evans and Spruck    and Chen, Giga, and Goto   proved in 1991 that
a continuous function moves by the curvature motion  with
$F(\mathrm{curv}(u), t)=\mathrm{curv}(u)$) if and only if almost
all of its level curves move by curve shortening. The same result
is true for the affine invariant curve evolution (equation
\eqref{curve} with $F(\mathrm{curv}(u),
t)=(\mathrm{curv}(u))^{1/3}$) and affine shortening.
\end{slide}\begin{slide}
In the case of the curvature motion, this result provides a
mathematical justification for the now-classic Osher--Sethian
numerical method for moving fronts. They associate with some curve
or surface $C$ its signed distance function $u(\fxx)=\pm
d(\fxx,C)$, and  the curve or surface is handled indirectly as the
zero isolevel set of $u$. Then $u$ is evolved by, say, the
curvature motion with a classic numerical difference scheme. Thus,
the evolution of the curve $C$ is dealt with efficiently and
accurately as a by-product of the evolution of $u$. The point of
view that we adopt is slightly different from that of Osher and
Sethian. We view the image as a generalized distance function to
each one of its level sets, since we are interested in all of
them.
\end{slide}\begin{slide}
We show in Figure \ref{IMGPREFACE19} how the level lines are
simplified by  evolving the image numerically using affine
invariant curvature motion. For clarity, we display only sixteen
levels of level curves. Notice that the aim here is not
subsampling; we keep the same resolution. Nor is the aim
restoration; the processed image is clearly worse than the
original. The aim is invariant simplification leading to shape
recognition.
\end{slide}
\begin{figure}[!ht]
\setkeys{Gin}{width=3cm}
\centerline{
\includegraphics{fig00.18.1.eps}
\includegraphics{fig00.18.2.eps}
\includegraphics{fig00.18.3.eps}
\includegraphics{fig00.18.4.eps}
}
\caption[The affine and morphological scale space]{\label{IMGPREFACE19} The affine and morphological scale space (AMSS model). Left to right: original image; level lines of this image (16 levels only); original image smoothed using the AMSS equation; level lines of the third image.}
\end{figure}

\begin{figure}[!ht]
\setkeys{Gin}{width=8cm} \centerline{
\includegraphics{fig00.20.1.eps}
}
\caption[Curvature scale space I]{ \label{curvaturescalespaceexperiment1}Curvature scale space I. Top, left to right: original sea bird image  smoothed by affine curvature motion at calibrated scale 1; the absolute value of the curvature. Bottom, left to right: the positive part of the curvature; the negative part. Compare with Figure I.22, where the calibrated smoothing scale is 4.
}
\end{figure}

\begin{figure}[!ht]
\setkeys{Gin}{width=8cm} \centerline{
\includegraphics{fig00.21.1.eps}
}
\caption[Curvature scale space II]{\label{curvaturescalespaceexperiment2}Curvature scale space II. Top, left to right: original sea bird image  smoothed by affine curvature motion at calibrated scale 4; the absolute value of the curvature. Bottom, left to right: the positive part of the curvature; the negative part.
Compare with Figure I.21, where the calibrated smoothing scale is 1.
}
\end{figure}
 \begin{slide}

A variant of the curvature equation can be used for shape
detection. A well-known method of contour detection, initially
proposed by Kass, Witkin, and Terzopoulos. A better method is a
variant of curvature motion proposed by Caselles, Catt\'{e}, Coll,
and Dibos and improved simultaneously by Caselles, Kimmel, and
Sapiro   and Malladi, Sethian, and Vemuri. The user draws roughly
the desired contour in the image, and the algorithm then finds the
best possible contour in terms of some variational criterion $E$.
Given an original image $u_0$ containing some closed contour that
we wish to approximate, we start with an edge map
\[
g(\fxx)=\frac 1{1+|Du_0(\fxx)|^2},
\]
that is, a function that vanishes on the edges of the image. The
user then designates the contour of interest by drawing a polygon
$\gamma_0$ roughly following the desired contour. The {\it
geodesic snake} algorithm then builds a distance function $v_0$ to
this initial contour, so that $\gamma_0$ is the zero level set of
$v_0$. The energy to be minimized is
\[
E(\gamma)=\int_\gamma g(\fxx(s))\,\mathrm{d}s,
\]
where $g$ is the edge map associated with the original image $u_0$ and $s$ denotes the parameter measuring the length along $\gamma$. The motion of the ``analyzing image" $v$ is governed by
\[
\frac {\partial v}{\partial t}(\bm{x},t) =g(\bm{x}) |Dv(\bm{x})|\mathrm{curv}(v)(\bm{x}) - Dv(\bm{x})\cdot Dg(\bm{x}).
\]
\end{slide}
\begin{figure}[!ht]
\setkeys{Gin}{width=3cm}
\centerline{
\includegraphics{fig00.22.1.eps}
\includegraphics{fig00.22.2.eps}
\includegraphics{fig00.22.3.eps}
\includegraphics{fig00.22.4.eps}
}
\caption[Active Contour]{\label{IMGPREFACE22}Active contour, or ``snake.'' Left to right: original image; initial contour; evolved distance function; final contour.}
\end{figure}


\begin{figure}[!t]
\setkeys{Gin}{width=6cm}
\centerline{
\includegraphics{fig00.23.1.eps}
\includegraphics{fig00.23.2.eps}
}
\caption[Level-lines based shape parser]{\label{IMGPREFACE20}
A shape parser based on level lines. The two left images are of a
desk and the backs of chairs viewed from different angles. In the far left panel, one level line has been put in white. In the second panel we show, also in white, the matching level lines. The match is ambiguous, as must be expected when the same object is repeated in the scene. In the two panels on the right, we display all the matching pairs of level lines in white.}
\end{figure}
