
\graphicspath{{./figures/}}

\chapter{Four Algorithms  to Smooth a Shape\label{chapfourways}}

In this short but important chapter, we discuss  algorithms whose
aim it is to smooth shapes. Shape must be understood as a rough
data which can be extracted from an image, either a subset of the
plane, or the curve surrounding it.  Shape smoothing is directed
at the elimination of spurious, often noisy, details. The smoothed
shape can then be reduced to a compact and robust code for
recognition. The choice of the right smoothing will make us busy
throughout the book.  A good part of the solution stems from the
four algorithms we describe and their progress towards more
robustness, more invariance  and more locality.  What we mean by
such qualities will be progressively formalized.  We will discuss
two algorithms which directly smooth {\it sets}, and two which
smooth Jordan curves. One of the aims of the book is actually to
prove that both  approaches, different though they are, eventually
yield the {\it very same process}, namely a curvature motion.


\section{Dynamic shape\label{sectiondynamicshape}}

In 1986, Koenderink and van Doorn defined a \textit{shape} in
$\RR^N$ to be a closed subset $X$ of $\RR^N$
\cite{Koenderink:1986:DS}. They then 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 this half plane doesn't move,
\[
X=X_t=\{(x,y)\mid G_t*\bmone_X(x,y)\geq\lambda\},
\]
and this is true only if $\lambda=1/2$. There are at least two
problems with dynamic shape evolution for image analysis. The
first concerns nonlocal interactions, as illustrated in Figure
\ref{fig210}. Here we have two disks that are near one another.
The evolution of the union of both disks, considered as a single
shape, is quite different from the evolution of the disks
separately. A related problem, also illustrated in Figure
\ref{fig210}, is the creation of singularities. Note how a
singularity in orientation and the curvature of the boundary of
the shape develops at the point where the two disks touch. Figure
\ref{fig29} further illustrates the problems associated with the
dynamic shape method.

\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. 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}


\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.
Thus, each curve  we consider can be represented by a continuous
mapping $f:[0,1]\to\RR^2$ such that $f$ is one-to-one on $(0,1)$
and $f(0)=f(1)$, and each curve has a finite length. We also
assume that these curves do not intersect each other. 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)$.

\begin{figure}[!t]
\setkeys{Gin}{width=4cm} \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 of shapes with the
dynamic shape method. This image displays the 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.
Compare with Figure \ref{fig212}. }
\end{figure}

At first glance, it might seem reasonable to smooth $C_0$ by
smoothing the coordinate functions $x$ and $y$ separately. If this
is done linearly, we have seen from Theorem 2.3 that the process
is asymptotic to smoothing with the heat equation. Thus, one is
led naturally to consider the vector heat equation
\begin{equation}\label{vheat}
\frac{\partial \fxx}{\partial t}(t,s)=\frac{\partial^2
\fxx}{\partial s^2}(t,s)
\end{equation}
with initial condition $\fxx(0,s)=\fxx_0(s)$. If
$\fxx(t,s)=(x(t,s),y(t,s))$ is the solution of \eqref{vheat}, then
we know from Proposition 1.9 that
\begin{align*}
\inf_{s\in[0,L]}x_0(s)&\leq x(t,s)\leq\sup_{s\in[0,L]}x_0(s),\\
\inf_{s\in[0,L]}y_0(s)&\leq y(t,s)\leq\sup_{s\in[0,L]}y_0(s),
\end{align*}
for $s\in[0,L]$ and $t\in[0,+\infty)$. Thus, the evolved curves
$C_t$ remain in the rectangle that held $C_0$. Also, we know from
Proposition \ref{proposition1.8} that the coordinate functions
$x(t,\cdot)$ and $y(t,\cdot)$ are $C^{\infty}$ for $t>0$. 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. In fact, it can be seen
from Figure \ref{fig211} that it is possible for an evolved curve
to cross itself and it is possible for it to develop
singularities.
\end{enumerate}
How is this last mentioned phenomenon possible ? It turns out that
one can parameterize a curve with corners or cusps with a very
smooth parameterization: see Exercise \ref{carreparametre}.

\begin{figure}[!t]
\setkeys{Gin}{width=6cm} \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}

In image processing, we say that a process that introduces new features, such as described in item (2) above, is not
\textit{causal}. \footnote{This informal definition should not be confused with the use of ``causality,'' as it is
used, for example, when speaking about filters: A filter $F$ is said to be causal, or realizable, if the equality of
two signals $s_0$ and $s_1$ up to time $t_0$ implies that $Fs_0(t)=Fs_1(t)$ for the same period.}



\section{Restoring locality and causality}

Our main objective is to redefine the smoothing processes so they are local and do not create new singularities. This
can be done by alternating a small-scale linear convolution with a natural renormalization process.

\subsection{Localizing the dynamic shape method}

In the case of dynamic shape analysis, we define an alternate
dynamic shape algorithm as follows:
\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}
This is an iterated dynamic shape algorithm. The dynamic shape method itself  is an example of a \textit{median
filter}, which will be defined in Chapter \ref{Chap9}. The Merriman--Bence--Osher algorithm is thus an \textit{iterated
median filter} (see Figure \ref{fig212}). We will see in Chapters \ref{Chap10} and \ref{ChapasymptoticdimensionN} that
median filters have asymptotic properties that are similar to those expressed in Theorem \ref{theorem2.3}. In the case
of median filters, the associated partial differential equation will be a curvature motion equation (defined in Chapter
\ref{Chap5}).

\begin{figure}[!t]
\setkeys{Gin}{width=4cm} \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 Merriman--Bence--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}

\subsection{Renormalized heat equation for curves}

In 1992, Mackworth and Mokhtarian noticed the loss of causality
when the heat equation was applied to curves
\cite{Mackworth:1992:TMC}. Their method to restore causality
looks, at least formally, like the remedy given for the
nonlocalization of the dynamic shape method. Instead of applying
the heat equation for relatively long times (or, equivalently,
convolving the curve $\fxx$ with the Gaussian $G_t$ for large
$t$), they use the following algorithm:
\begin{algorithm}[Renormalized heat equation for curves]\leavevmode
\begin{enumerate}[(1)]\setlength\itemsep{2pt}\label{algorithm2.4}
\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}

This algorithm is illustrated in Figure \ref{fig213}. It should be compared with Figure \ref{fig211}.

\begin{theorem} \label{theorem2.5} 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).
\end{equation}
\end{theorem}
This theorem is easily checked, see Exercise \ref{proofofthm2.5}


\begin{figure}[!t]
\setkeys{Gin}{width=6cm} \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}



In view of \eqref{225} and what we have seen regarding asymptotic
limits in Theorem \ref{theorem2.3} and Exercise \ref{exercise2.4},
it is reasonable to conjecture that, in the asymptotic limit,
Algorithm \ref{algorithm2.4} 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 \eqref{vheat}.
Indeed, from Algorithm \ref{algorithm2.4} we see that $s$ must denote the length parameter of the evolved curve
$\fxx(t,\cdot)$ at time $t$. In fact ${\partial^2 \fxx}/{\partial s^2}$ has a geometric interpretation as a curvature
vector. We will study this nonlinear curve evolution equation in Chapter \ref{Chap5}.

\section{Exercises}


\begin{exercise}\label{carreparametre}
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}

\begin{exercise}\label{proofofthm2.5}
Prove Theorem \ref{theorem2.5}. If $\fxx$ is a $C^3$ function of
$s$, then the result follows directly from Theorem
\ref{theorem2.2}. The result holds, however, for a $C^2$ curve.
\finex
\end{exercise}

\section{Comments and references}

\paragraph*{Dynamic shape, curve evolution, and restoring causality.}
 Our account of the dynamic shape method is based on the well-known paper by
 Koenderink and van Doorn in which they introduced this notion \cite{Koenderink:1986:DS}.
 The curve evolution by the heat equation is from the first 1986 version of curve analysis
  proposed by Mackworth and Mokhtarian \cite{Mackworth:1986:SBD}. See also
  the paper by Horn and Weldon \cite{Horn:1986:FCC}. There were model
errors in the 1986 paper \cite{Mackworth:1986:SBD} that were corrected by the authors in their 1992 paper
\cite{Mackworth:1992:TMC}. There, they also proposed the correct intrinsic equation. However, this 1992 paper contains
several inexact statements about the properties of the intrinsic equation. The correct theorems and proofs can be found
in a paper by Grayson written in 1987 \cite{Grayson:1987:HESb}.  The algorithm that restores
  causality and locality to the dynamic shape method was discovered by Merriman,
   Bence, and Osher, who devised this algorithm for a totally different reason:
They were looking for a  clever numerical implementation of the mean curvature equation \cite{Merriman:1992:DGM}.

\paragraph*{Topological change under smoothing.} We have  included several figures that
illustrate how essential topological properties of an image change
when the image is
 smoothed with the Gaussian. Damon has made a complete analysis of the topological behavior
 of critical points of an image under Gaussian smoothing \cite{Damon98}.
 This analysis had been sketched in \cite{Yuille:1988:CSD}.





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