%gmChap02.tex

%\graphicspath{{./figures/chapter02/}}

\section{Applications of the Heat Equation to Image Analysis}


\subsection{Convergence of iterated filters to the heat equation}

We wish to prove that iterated linear smoothing is asymptotic to
applying the heat equation, or equivalently, to convolution with
the Gaussian at different scales.

\begin{definition}
We say that a real-valued  kernel $g\in L^1(\RR^N)$ is Laplacian
consistent if it satisfies the following moment conditions:
\begin{enumerate}%[$(i)$]%\setlength\itemsep{2pt}
\item $\int_{\RR^N} g(\fxx)\,\rmd\fxx=1.$
\item For $i=1,2,\ldots,N$, $\int_{\RR^N} x_ig(\fxx)\,\rmd\fxx=0.$
\item For each pair $i,j=1,2,\ldots,N$, $i\neq j$,
$\int_{\RR^N}x_i x_jg(\fxx)\,\rmd\fxx=0.$
\item For $i=1,2,\ldots,N$, $\int_{\RR^N} x_i^2g(\fxx)\,\rmd\fxx=\sigma,$ where $\sigma>0.$
\item $\int_{\RR^N}|\fxx|^3|g(\fxx)|\,\rmd\fxx<+\infty.$
\end{enumerate}
\end{definition}

 \begin{slide}
We consider rescalings of a kernel $g$ defined by
\begin{equation}\label{gh}
g_h(\fxx)=\frac{1}{h^{{N}/{2}}}\,g\Big(\frac{\fxx}{h^{{1}/{2}}}\Big)
\end{equation}
for $h>0$.
\begin{figure}[!t]
\setkeys{Gin}{width=10cm} \centerline{
\includegraphics{fig02.01.1.eps}
} \caption[Kernel rescaling]{\label{fig21}The rescalings
$g_t(\fxx)= ({1}/{t^2}) g({\fxx}/{t})$ of a kernel for t=4, 3, and
2.}
\end{figure}
\end{slide}
\begin{slide}

 We denote the convolution of
$g$ with itself $n$ times by $g^{n*}$. The main result of this
section concerns the behavior of $g_h^{n*}$ as $n\to+\infty$ and
$h\to0$.



\begin{theorem} If $g$ is Laplacian consistent, then for every $u\in L^{\infty}_C\cap C^3$,
\begin{equation}\label{LC}
g_h*u(\fxx)-u(\fxx)=h\frac{\sigma}{2}\Delta u(\fxx)+\varepsilon(h,\fxx)
\end{equation}
where $|\varepsilon(h,\fxx)|\leq Ch^{3/2}$.
\end{theorem}
\end{slide}
\begin{proof}
\begin{align*}
g_h*u(\fxx)-u(\fxx)=&\int_{\RR^N}\frac{1}{h^{{N}/{2}}}\,g\Big(\frac{\fxx}{h^{{1}/{2}}}\Big)\big(u(\fxx-\fxy)-u(\fxx)\big)\,\rmd\fxy\\
=&\int_{\RR^N}g(\fxz)\big(u(\fxx-h^{1/{2}}\fxz)-u(\fxx)\big)\,\rmd\fxz.
\end{align*}
Using Taylor's formula with the Lagrange remainder, we have
\[
u(\fxx-h^{1/{2}}\fxz)-u(\fxx)=-h^{1/{2}}Du(\fxx)\cdot\fxz+\frac{h}{2}D^2u(\fxx)(\fxz,\fxz)-\frac{1}{6}h^{3/{2}}D^3u(\fxx-h^{1/{2}}\theta\fxz)(\fxz,\fxz,\fxz),
\]
where $\theta=\theta(\fxx, \fxz,h)\in [0,1]$. By condition $(1)$,
$\int_{\RR^N}g(\fxz)Du(\fxx)\cdot\fxz\,\rmd\fxz=0$; by conditions
$(3)$ and $(4)$,
$\int_{\RR^N}g(\fxz)D^2u(\fxx)(\fxz,\fxz)\,\rmd\fxz=\sigma\Delta
u(\fxx)$. Thus,
\[
g_h*u(\fxx)-u(\fxx)=h\frac{\sigma}{2}\Delta u(\fxx)-\frac{1}{6}h^{3/{2}}\int_{\RR^N}g(\fxz)D^3u(\fxx-h^{1/{2}}\theta\fxz)(\fxz,\fxz,\fxz)\,\rmd\fxz.
\]
\end{proof}

\begin{slide}

\begin{theorem}Let $g$ be a nonnegative Laplacian-consistent
kernel with $\sigma=2$ and define $g_h$ by \eqref{gh}. Write
 $T_hu_0=g_h*u_0$ for $u_0\in L^1_C$, and let $u(t,\cdot)=G_t*u_0$
  be the solution of the heat equation \eqref{heatsol}. Then, for each $t>0$,
\begin{equation}\label{37}\addtolength\belowdisplayskip{-12pt}
T_h^nu_0\to u(t,\cdot)\,\text{ in }\, L^1(C)\,\text{ as }
\, n\to+\infty\,\text{ and }\, nh\to t.
\end{equation}
\end{theorem}
\end{slide}


\begin{figure}[!t]
\setkeys{Gin}{width=10cm}
\centerline{\includegraphics{fig02.02.1.eps}}
\caption[Iterated linear smoothing converges to the heat equation]{\label{22}Iterated linear smoothing converges to the heat equation. In this
experiment with one-dimensional functions, it can be appreciated how
fast an iterated convolution of a positive kernel converges to a
Gaussian. On the left are displayed nine iterations of the convolution of the characteristic function of an interval with itself, with appropriate rescalings. On the right, the same experiment is repeated with a much more irregular kernel. The convergence is almost as fast as the first case.}
\end{figure}

\begin{slide}
{\Large Proof}
\begin{equation}\label{38}
T_hu(t,\fxx)-u(t,\fxx)=h\Delta u(t,\fxx)+O(h^{{3}/{2}}),
\end{equation}
 Since $u$ is a solution of the heat
equation, we also have
\begin{equation}\label{39}
u(t+h,\fxx)-u(t,\fxx)=h\Delta u(t,\fxx)+O(h^2).
\end{equation}
 By subtracting \eqref{39} from
\eqref{38} we see that
\begin{equation}\label{310}
T_hu(t,\fxx)=u(t+h,\fxx)+O(h^{{3}/{2}}).
\end{equation}
This shows that applying $T_h$ to a solution  of the heat equation
at time $t$ advances the solution to time $t+h$, plus an error
term.
\end{slide}
\begin{slide}
\Large{Proof}
 We can apply $T_h$ to both sides of \eqref{310} and obtain
\begin{equation}\label{311}
T^2_hu(t,\fxx)=T_hu(t+h,\fxx)+O(h^{{3}/{2}}).
\end{equation}
If we write equation \eqref{310} with $t+h$ in place  of $t$ and
substitute the expression for $T_hu(t+h,\fxx)$ in equation
\eqref{311}, we have
\begin{equation}
T^2_hu(t,\fxx)=u(t+2h,\fxx)+2O(h^{{3}/{2}}).
\end{equation}
We can iterate this process and get the relation
\begin{equation}
T^n_hu(t,\fxx)=u(t+nh,\fxx)+nO(h^{{3}/{2}}).
\end{equation}
Take $t=t_1$ and $h=\tau/n$. Then
\begin{equation}\label{315}
T^n_hu(t_1,\fxx)=u(t_1+\tau,\fxx)+O\Big(\Big(\frac{\tau}{n}\Big)^{{1}/{2}}\Big)
\end{equation}
and
\begin{equation}
\lim_{n\to+\infty\atop nh=\tau}T^n_hu(t_1,\fxx)=u(t_1+\tau,\fxx).
\end{equation}
 \hfill

\end{slide}



\section{Directional averages and directional heat equations}

The purpose of this section is to show how to approximate
directional second derivatives using local averages. Consider a
$C^2$ function from $\RR^N$ into $\RR$ and a vector $\fxz\in\RR^N$
with $|\fxz|=1$. We wish to compute the mean value of $u$ along a
segment of the line through $\fxx$ parallel to the vector $\fxz$.
To do this, we define the operator $T^{\fxz}_h$, $h\in[-1,1]$, by
\[
T^{\fxz}_hu(\fxx)=\frac{1}{2h}\int_{-h}^h u(\fxx+s\fxz)\,\rmd s.
\]
  We use Taylor's formula
to expand $u$ at the point $\fxx$ along the line through $\fxx$
parallel to the vector $\fxz$:
\begin{equation}\label{linez}
u(\fxx+s\fxz)=u(\fxx)+sDu(\fxx)\cdot\fxz+\frac{s^2}{2}D^2u(\fxx)(\fxz,\fxz)+o(s^2).
\end{equation}
By averaging both sides of \eqref{linez} over $s\in[-h,h]$, we obtain the next result.
\begin{proposition}
\[
T^{\fxz}_hu(\fxx) =\frac{1}{2h}\int_{-h}^h
u(\fxx+s\fxz)=u(\fxx)+\frac{h^2}{6}D^2u(\fxx)(\fxz,\fxz)+o(h^2).
\]
\end{proposition}
This  suggests that iterations of the operator $T^{\fxz}_h$ are
associated with the directional heat equation
\begin{equation}\label{dirheateqn1}
\frac{\partial u}{\partial t}(t,\fxx)=\frac{1}{6}D^2u(t,\fxx)(\fxz,\fxz)
\end{equation}



This is correct under the assumption that $\fxz$ is fixed. We are
able to approximate the directional second derivative by taking
directional averages when $\fxz$ varies from point to point. The
main choice considered in the book is $\fxz={Du^{\perp}}/{|Du|}$,
where $Du=(u_x,u_y)$ and $Du^{\perp}=(-u_y,u_x)$.


\begin{slide}
\begin{enumerate}%[$\bullet$]\setlength\itemsep{2pt}
\item Average in the direction of the gradient. By choosing $z={Du}/{|Du|}$,
\[
u_{\xi\xi}=\frac{1}{|Du|^2}D^2u(Du,Du)=6\lim_{h\to0}\frac{T^{Du/|Du|}_hu-u}{h^2}.
\]
We will interpret this differential operator as Haralick's edge
detector. \item Average in the direction orthogonal to the
gradient. By choosing $z={Du}/{|Du^\perp|}$,
\[
\frac{1}{|Du|^2}D^2u(Du^\perp,Du^\perp)=6\lim_{h\to0}\frac{T^{Du^\perp/|Du|}_hu-u}{h^2}.
\]
This differential operator appears as the second term of the curvature equation.
\end{enumerate}
\end{slide}

\begin{exercise} Suppose that $u\in C^2(\RR)$.
If $Du(\fxx)\not=0$,  prove  that
\begin{equation}\label{ex253}
u_{\xi\xi}(\fxx)=\lim_{h\to0}\frac{1}{h^2}\Big(\max_{\fxy\in D(0,h)}u(\fxx+\fxy)+\min_{\fxy\in D(0,h)}u(\fxx+\fxy)-2u(\fxx)\Big),
\end{equation}
where $D(0,h)$ is the disk of radius $h$ centered at the origin.
  \finex
\end{exercise}

\begin{slide}
\section{Edge detection and linear scale space}

The general analysis framework in which an  image is associated
with smoothed versions of itself at several scales is called
\textit{scale space}. We are first going to discuss some of the
ways linear smoothing has been used in image analysis. We will
then indicate the problems associated with the linear theory.

\end{slide}
\begin{slide}
\subsection{The edge detection doctrine}

\begin{algorithm}[Edge detection: Marr--Hildreth zero-crossings]\leavevmode
\begin{enumerate}%[(1)]\setlength\itemsep{2pt}
\item Create the multiscale images $u(t,\cdot)=G_t*u_0$ for
increasing values of $t$. \item At each scale $t$, compute all the
points where $\Delta u$ changes sign and $Du\not=0$. These points
are called zero-crossings of the Laplacian, or simply
zero-crossings. \item (Optional) Eliminate the zero-crossings
where the gradient is small.
\end{enumerate}
\end{algorithm}

\end{slide}


\begin{figure}[!t]
\setkeys{Gin}{width=8cm} \centerline{
\includegraphics{fig02.03.1.eps}
} \caption[The Laplacian of the Gaussian]{\label{fig23}A
three-dimensional representation of the Laplacian of the Gaussian.
This convolution kernel, which is a wavelet, is used to estimate
the Laplacian of an image at different scales of linear
smoothing.}
\end{figure}


\begin{figure}[!h]
\setkeys{Gin}{width=10cm} \centerline{
\includegraphics{fig02.04.1.eps}
} \caption[Zero-crossing of the Laplacian at different
scales]{\label{fig24} Zero-crossings of the Laplacian at different
scales (David Marr). To extract more global structure, the image
is convolved with Gaussians whose variances are powers of two. One
computes the Laplacian of the smoothed image and displays the
lines along which this Laplacian changes sign: the zero-crossings
of the Laplacian. According to Marr, these zero-crossings
represent the ``raw primal sketch" of the image, or the essential
information on which further vision algorithms should be based.
Above, left to right: the results of smoothing and the associated
Gaussian kernels at scales 1, 2, and 4. Below, left to right: the
zero-crossings of the Laplacian and the corresponding kernels,
which are the Laplacians of the Gaussians used above.}
\end{figure}

\begin{slide}
   Haralick gives up linearity and define edge points as
those points where the gradient has a local maximum in the
direction of the gradient. In other words, an edge point $\fxx$
satisfies $g'(0)=0$, where $g(t)=|Du(\fxx+tDu(\fxx)|/|Du(\fxx)|$.
This implies that $D^2u(\fxx)(Du(\fxx),Du(\fxx))=0$.


\begin{exercise}
Check that $g'(0)=0$ implies that $D^2u(\fxx)(Du(\fxx),Du(\fxx))=0$. \finex
\end{exercise}
\end{slide}

\begin{slide}
\begin{algorithm}[Edge detection: The Haralick--Canny edge detector]\leavevmode
\begin{enumerate}%[(1)]\setlength\itemsep{2pt}
\item As before, create the multiscale images $u(t,\cdot)=G_t*u_0$ for increasing values of $t$.
\item At each scale $t$, find all points $\fxx$ where $Du(\fxx)\not=0$ and $D^2u(\fxx)(\fxz,\fxz)$ crosses zero, $\fxz=Du/|Du|$. At such points, the function $s\mapsto u(\fxx+s\fxz)$ changes from concave to convex, or conversely, as $s$ passes through zero.
\item At each scale $t$, fix a threshold $\theta(t)$ and retain as \textit{edge points at scale} $t$ only those points found above that satisfy $|Du(\fxx)|>\theta(t)$.
\end{enumerate}
\end{algorithm}


\noindent In practice, edges are computed for a finite number of dyadic scales, $t=2^n$, $n\in\ZZ$.
\end{slide}





\begin{figure}[!t]
\setkeys{Gin}{width=8cm} \centerline{
\includegraphics{fig02.06.1.eps}
} \caption[Haralick-Canny's edge detector]{\label{fig26}Canny's
edge detector.   Left column: result of the Canny filter without
the threshold on the gradient. Middle column: result with a
visually ``optimal'' scale and an image-dependent threshold (from
top to bottom: 15, 0.5, 0.6). Right column: result with a fixed
gradient threshold equal to 0.5. Note that this edge detection
``theory'' depends on no fewer than three parameters that must be
fixed by the user. }
\end{figure}





\begin{figure}[!t]
\setkeys{Gin}{width=10cm}
\centerline{
\includegraphics{fig02.05.1.eps}
}
\caption[Zero-crossings of the Laplacian of a synthetic image]{\label{fig25}Zero-crossings of the Laplacian of a synthetic image. Left to right: the original image; the image linearly smoothed by convolution with
a Gaussian; the sign of the Laplacian of the filtered image (the gray color corresponds to values close to 0, black to clear-cut negative values, white to clear-cut positive values); the zero-crossings of the Laplacian. This experiment clearly shows a drawback of the Laplacian as edge detector.
}
\end{figure}

\begin{figure}[!ht]
\setkeys{Gin}{width=10cm}
\centerline{
\includegraphics{fig02.08.1.eps}
} \caption[The heat equation creates structure.]{\label{fig28} The
heat equation creates structure. This experiment shows that linear
scale space can create new structures and thus increase the
complexity of an image. Left to right: The original synthetic
image (a) contains three gray levels. The black disk is a regional
and absolute minimum. The ``white'' ring around the black disk is
a regional and absolute maximum. The outer gray ring has a gray
value between the other two and is a regional minimum. The second
image (b) shows what happens when (a) is smoothed with the heat
equation: New extrema have appeared. Image (c) illustrates the
action on (a) of a contrast-invariant local filter, the iterated
median filter. }
\end{figure}

\begin{figure}[!ht]
\setkeys{Gin}{width=5cm} \centerline{
\includegraphics{fig02.07.1.eps}
}
%\centerline{
%\includegraphics{fig02.07.2.eps}
%}
\caption[Violation of the shape inclusion  principle by the linear
scale space]{\label{fig27}Violation of the inclusion by the linear
scale space. Top, left: an image that contains a black disk
enclosed by a white disk. Top, right: At a certain scale, the
black and white circles mix together. Bottom level lines of the
above images: the inclusion is no longer preserved.   }
\end{figure}

\begin{slide}
{\Large Contrast invariance}


 If image analysis is to be robust, it must be invariant under
changes in lighting that produce contrast changes. It must also be
invariant under the nonlinear response of the sensors used to
capture an image. These, and perhaps other, contrast changes are
modeled by $g$  strictly increasing. A problem with linear theory
is that linear smoothing, that is, convolution, is not generally
contrast invariant:
\[
g(k*u)\not=k*(g(u)).
\]
\end{slide}
\begin{slide}
In the same way, the operator $T_t$ that maps $u_0$ into the solution of the heat equation, $u(t,\cdot)$ is not generally contrast invariant. In fact, if $g$ is $C^2$, then

\begin{align*}
\frac{\partial(g(u))}{\partial t}&=g'(u)\frac{\partial u}{\partial t}\\[-2ex]
\intertext{and}\\[-5ex]
\Delta(g(u))&=g'(u)\Delta u + g''(u)|Du|^2.
\end{align*}
Of course, if $g$ is linear, then $g(u)$ satisfies the heat equation if $u$ does.

\begin{exercise}
Construct simple functions $u$, $g$, and $k$ such that $g(k*u)\not=k*(g(u))$. \finex
\end{exercise}

\end{slide}
\begin{slide}
{\Large The heat equation : fours ways to smooth a shape}

\end{slide}

\begin{slide}
\section{Dynamic shape}

In 1986, Koenderink and van Doorn defined a  \textit{shape} in
$\RR^N$ to be a closed subset $X$ of $\RR^N$
 and proposed to smooth the shape
by applying the heat equation $\partial u/\partial t-\Delta u=0$
directly to $\bmone_X$, the characteristic function of $X$. Of
course, the solution $G_t*\bmone_X$ is not a characteristic
function. The authors defined the evolved shape at scale $t$ to be
\[
X_t=\{\fxx\mid u(t,\fxx)\geq 1/{2}\}.
\]
The value $1/2$ is chosen so the following simple requirement is satisfied: Suppose that $X$ is the half-plane $X=\{(x,y)\mid (x,y)\in\RR^2, x\geq0\}$. The requirement is that
\[
X=X_t=\{(x,y)\mid G_t*\bmone_X(x,y)\geq\lambda\},
\]
and this is true only if $\lambda=1/2$.
\end{slide}

\begin{figure}[!t]
\setkeys{Gin}{width=3cm}
\centerline{
\includegraphics{fig02.10.1.eps}\hspace{-10pt}
\includegraphics{fig02.10.2.eps}\hspace{-10pt}
\includegraphics{fig02.10.3.eps}\hspace{-10pt}
\includegraphics{fig02.10.4.eps}
} \caption[Dynamic shape and nonlocal
interactions.]{\label{fig210}  Nonlocal interactions in the
dynamic shape method and the creation of singularity  (Alan Yuille
: ``The creation of structure in dynamic shape"). Left to right:
Two close disks interact as the scale increases. This creates a
new, qualitatively different, shape. The change of topology, at
the scale where the two disks merge into one shape, also entails
the appearance of a singularity (a cusp) on the shape(s)
boundaries.}
\end{figure}

\begin{figure}[!t]
\setkeys{Gin}{width=3cm} \centerline{
\includegraphics{fig02.09.1.eps}\hspace{-4pt}
\includegraphics{fig02.09.2.eps}\hspace{-4pt}
\includegraphics{fig02.09.3.eps}
}\vspace{-20pt} \centerline{
\includegraphics{fig02.09.4.eps}\hspace{-4pt}
\includegraphics{fig02.09.5.eps}\hspace{-4pt}
\includegraphics{fig02.09.6.eps}
} \caption[Dynamic shape, nonlocal behavior of
shapes.]{\label{fig29}  Nonlocal behavior   with the dynamic shape
method. Smoothing of two irregular shapes by the dynamic shape
method (Koenderink--van Doorn). Top left: initial image, made of
two irregular shapes. From left to right, top to bottom: dynamic
shape smoothing with increasing Gaussian variance. Notice how the
shapes merge more and more. We do not have a separate analysis of
each shape but rather a ``joint analysis'' of the two shapes. The
way the shapes merge is of course sensitive to the initial
distance between the shapes.
  }
\end{figure}

\begin{slide}
\section{Curve evolution using the heat equation}

We consider shapes in $\RR^2$ whose boundaries can be represented
by a finite number of simple closed rectifiable Jordan curves.
  We will
focus on smoothing one of these Jordan curves, which we call
$C_0$. We assume that $C_0$ is parameterized by $s\in[0,L]$, where
$L$ is the length of the curve. Thus, $C_0$ is represented as
$\fxx_0(s)=(x(s),y(s))$, where $s$ is the length of the curve
between $\fxx_0(0)$ and $\fxx_0(s)$.
\end{slide}

\begin{slide}
 At first glance, it might seem reasonable to  smooth $C_0$
by smoothing the coordinate functions $x$ and $y$ separately.
\begin{equation}\label{vheat}
\frac{\partial \fxx}{\partial t}(t,s)=\frac{\partial^2
\fxx}{\partial s^2}(t,s),\;\;\; \fxx(0,s)=\fxx_0(s).
\end{equation}
By the maximum principle, the evolved curves $C_t$ remain in the
rectangle that held $C_0$ and $x(t,\cdot)$ and $y(t,\cdot)$ are
$C^{\infty}$. There are, however, at least two reasons that argue
against smoothing curves this way:
\begin{enumerate}%[(1)]\setlength\itemsep{2pt}
\item When $t>0$, $s$ is no longer a length  parameter for the
evolved curve $C_t$.
 \item Although $x(t,\cdot)$ and $y(t,\cdot)$
are $C^{\infty}$ for $t>0$, this does not imply that the curves
$C_t$ have similar smoothness properties. It is possible for an
evolved curve to cross itself and  to develop singularities.
\end{enumerate}
\end{slide}

\begin{figure}[!t]
\setkeys{Gin}{width=5cm} \centerline{
\includegraphics{fig02.11.1.eps}
\includegraphics{fig02.11.2.eps}
}
\centerline{
\includegraphics{fig02.11.3.eps}
\includegraphics{fig02.11.4.eps}
}
\caption[Curve evolution by the heat equation.]{\label{fig211} Curve evolution by the heat equation. The coordinates of the curves are parameterized by the arc length and then smoothed as real functions of the length using the heat equation. From A to D: the coordinates are smoothed with an increasing scale. Each coordinate function therefore is $C^\infty$;  the evolving curve can, however, develop self-crossings (as in C) or singularities (as in D).}
\end{figure}
\begin{slide}

\begin{exercise}
Construct a $C^{\infty}$ mapping $f:[0,1]\to\RR^2$ such that the
image of $[0,1]$ is a square. This shows that a curve can have a
$C^{\infty}$ parameterization without being smooth. \finex
\end{exercise}
\medskip The fact that curves with corners can be described  by a
$C^2$ parameterization is used in the seminal paper by Kass,
Witkin and Terzopoulos on ``snakes, active contour models" (1988).


\end{slide}

\begin{slide}

\section{Restoring locality and causality}

\subsection{Localizing the dynamic shape method}

 \begin{algorithm}[The Merriman--Bence--Osher algorithm]\leavevmode
\begin{enumerate}%[(1)]\setlength\itemsep{2pt}
\item Convolve the characteristic function of the initial shape $X_0$ with $G_h$, where $h$ is small.
\item Define $X_1=\{\fxx\mid G_h*\bmone_{X_0}\geq 1/2\}$.
\item Set $X_0=X_1$ and go back to (1).
\end{enumerate}
\end{algorithm}
  The dynamic shape method itself  is an example of a \textit{median
  filter}.
\end{slide}

\begin{figure}[!t]
\setkeys{Gin}{width=3cm} \centerline{
\includegraphics{fig02.12.1.eps}\hspace{-4pt}
\includegraphics{fig02.12.2.eps}\hspace{-4pt}
\includegraphics{fig02.12.3.eps}
}\vspace{-20pt}
\centerline{
\includegraphics{fig02.12.4.eps}\hspace{-4pt}
\includegraphics{fig02.12.5.eps}\hspace{-4pt}
\includegraphics{fig02.12.6.eps}
}
\caption[Localized, iterated version of the dynamic shape.]{\label{fig212} The Bence--Merriman--Osher shape smoothing method is a localized and iterated version of the dynamic shape method. A convolution of the binary image with small-sized Gaussians is alternated with mid-level thresholding.  It uses the same initial data (top, left) as in Figure \ref{fig29}.  From left to right, top to bottom: smoothing with increasing scales. Notice that the shapes remain separate. In fact, their is no interaction between the evolving shapes. Each one evolves as if the other did not exist.
}
\end{figure}

\begin{slide}
\subsection{Renormalized heat equation for curves}

In 1992, Mackworth and Mokhtarian :
\begin{algorithm}[Renormalized heat equation for curves]\leavevmode
\begin{enumerate}%[(1)]\setlength\itemsep{2pt}
\item Convolve the initial curve $\fxx_0$, parameterized by its length parameter $s_0\in[0,L_0]$, with the Gaussian $G_h$, where $h$ is small.
\item Let $L_n$ denote the length of the curve $\fxx_n$ obtained after $n$ iterations and let $s_n$ denote its length parameter. For $n\geq1$, write $\tilde\fxx_{n+1}(s_n)=G_h*\fxx_n(s_n)$. Then reparameterize $\tilde\fxx_{n+1}$ by its length parameter $s_{n+1}\in[0,L_{n+1}]$, and denote it by $\fxx_{n+1}$.
\item Iterate.
\end{enumerate}
\end{algorithm}

\end{slide}

\begin{slide}
\begin{theorem} Let $\fxx$ be a $C^2$
curve parameterized by its length parameter $s\in[0,L]$. Then for small $h$,
\begin{equation}\label{225}
G_h*\fxx(s)-\fxx(s)=h\frac{\partial^2 \fxx}{\partial s^2}
+o(h)(=h\;Curv(x) + o(h).
\end{equation}
\end{theorem}
\end{slide}

\begin{figure}[!t]
\setkeys{Gin}{width=5cm} \centerline{
\includegraphics{fig02.13.1.eps}
\includegraphics{fig02.13.2.eps}
}
\centerline{
\includegraphics{fig02.13.3.eps}
\includegraphics{fig02.13.4.eps}
}
\caption[Curve evolution by the renormalized heat equation.]{\label{fig213} Curve evolution by the renormalized heat equation (Mackworth--Mokhtarian). After each smoothing step, the coordinates of the curve are reparameterized by the arc length of the smoothed curve. From A to D: the curve is smoothed with an increasing scale. Note that, in contrast with the linear heat equation (Figure \ref{fig211}), the evolving curve shows no singularities and does not cross itself.}
\end{figure}


 It is reasonable to
conjecture that, in the asymptotic limit, the renormalized shape
scale space will yield the solution of following evolution
equation:
\begin{equation}\label{226}
\frac{\partial \fxx}{\partial t}=\frac{\partial^2 \fxx}{\partial s^2},
\end{equation}
where $\fxx_0=\fxx(0,\cdot)$. It is important to note  that
\eqref{226} is \textit{not} the heat equation. Indeed, from the
Algorithm we see that $s$ must denote the length parameter of the
evolved curve $\fxx(t,\cdot)$ at time $t$. Since ${\partial^2
\fxx}/{\partial s^2}$ is the curvature vector $\text{Curv}(\fxx)$,
this is easier to remember if we write \eqref{226} as
\[
\frac{\partial \fxx}{\partial t}=\text{Curv}(\fxx).
\]





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