

\section [Morphological (set evolution) schemes.]{Morphological (set evolution) schemes.}

\subsection [A theoretical scheme.]{A theoretical scheme.}

In this subsection, we discuss theoretical schemes inspired from the set-theory of the Mathematical Morphology
School. Denote by $C$ a set of convex sets which is stable
 either by isometries or by linear maps. For
example, we can take for $C$ the set of disks, or the set of ellipses, or the set of triangles,...
And, for all $t\geq 0$ , we set
$$ C_t(x) = \{ B \in C ,\qquad \hbox{area}(B) = t^{3/2} ,
\qquad \hbox{ and x is the barycenter of }  B  \} $$

Then, we define two operators 
$$ IS_t (u)(x) = \inf_{B \in C_t(x)} ( \sup_{y \in  B} ( u(y)) $$
$$ SI_t (u)(x) = \sup_{B \in C_t(x)} ( \inf_{y \in  B} ( u(y)) $$ 


For example, if we take for $C$ the set of the circles, then $IS_t$ is the
 "closing" of radius t, and $SI_t$ is the "opening" of radius t which are wellknown
operators of the mathematical morphology [Serra].
If we impose that $C$ is stable by all linear maps, we obtain 
"special" opening and closing which verify \AFFI and which are clearly not idempotent.
 Consider the schemes

$$ \hbox{(i)} \qquad u^{n+1} = IS_{\Delta t}(u^n) $$
$$ \hbox{(ii)} \qquad u^{n+1} = SI_{\Delta t}(u^{n}) $$

It is proved in [LaMo] that the scheme (i) converges to the equation
 $$ \ut& = \vert Du \vert (curv^+(u))^{1/3} $$
and that the scheme (ii) converges to the equation 
$$ \ut& = \vert Du \vert (curv^-(u))^{1/3} .$$

\skipaline

In order to approximate equation (1), we alternate affine closing and
affine opening and we are led to the scheme:
$$ \hbox{(iii)} \qquad \left\{ \begin{array}{rcl} u^{n+\frac{1}{2}}(x) & = &
\inf_{B \in C_t(x)} ( \sup_{y \in  B} ( u^n(y))) \\
u^{n+1}(x) & = & \sup_{B \in C_t(x)} ( \inf_{y \in B} ( u^{n+\frac{1}{2}}(y)))
\end{array}
\right. $$

\skipaline

The mathematical morphology framework also leads naturally to the scheme

$$ \hbox{(iv)} \qquad u^{n+1}(x) = \med_{B\in C_t(x)}(\med_{y\in  B}(u^n(y))) $$
If $A$ is a finite set of real numbers, we call $med(A)=a$ any real number
such that Card$\{r \in A, r\ge a\}=$Card$\{r \in A, r\le a\}$. Of course, the possible
$a$'s make an interval and if we want to specify $a$, we take for $a$ the 
middle point of this interval.
\skipaline

All of these schemes satisfy:

\noindent  \STAB, \MONO and \Morp.

Lasry-Morel [LaMo] have introduced the schemes (i), (ii) and (iii) and proved their convergence.
And we conjecture for (iii) and (iv) that convergence is true for equation (\ref{m2cm}), if the set $C$
is stable by affinity for convenient values of $\Delta t$ and $n$. Evans [Eva] and Barles [Bar] proved that convergence is true for equation (\ref{eq:mcm}) and the scheme (iv), when the set $C$
is reduced to one disk with radius $t^{1/2}$ (see more details below). Among the schemes discussed in this paper, the 
morphological schemes (i)-(iv) discretized on a fixed grid are the only ones to be both morphological and orderpreserving.
(Whatever discretization of sup, inf, med on the grid is.)

But, they have not all geometrical properties. They satisfy only the
geometrical invariance of the grid and do not satisfy \ECHE.
Of course, their numerical implementation "\`a la lettre" is problematic.
It could be tried however by using a fast Legendre transform recently proposed by Y. Brenier [Bre].

\skipaline

\subsection [Iterated median filters and curvature motion.]{Iterated median filters and curvature motion.}

Variants of (4) have been proposed by Koenderink - Van Doorn [ KoDo ] and Merriman-Bence-Osher [MBO].
They define a weighted medium filter which weighs the contribution of points $y$ close to
a point $x$ according to a gaussian law of distance. So the algorithm can be rewritten
( when applied to a characteristic function $\tilde u^0$ of a level set) 

\skipaline

\begin {enumerate}

\item We define the image $\tilde u^0$ by :
$$\left \{ \begin{array}{l} \tilde u^0(x) =1 \; \; \; 
\hbox{if } x  \hbox{ belongs to the level set E }
\\ \tilde u^0(x) =0 \; \; \; \hbox{else.} \end{array} \right. $$

\item We solve the heat equation, with initial datum $\tilde u^n$, for a small time 
 $\Delta t$, by a convolution with a gauss function. We obtain a new
function $v^n$.

\item We set (median filter !)
$$\left \{ \begin{array}{l} \tilde  u^{n+1}(x) = 1 \; \; \;
\hbox{if } v^n(x) \geq \frac{1}{2} \\ \tilde  u^{n+1}(x) = 0 \; \; \;
\hbox{else } \end{array} \right. $$

\item We turn back to step 2.
\end {enumerate}

\skipaline

Evans [Eva] and independently, Barles-Georgelin [BaGe], proved that this theoretical scheme is consistent and convergent.
Earlier works of Yuille [Yui] and Mascarenhas [Masc] proved the consistency.
However, we shall see that its implementation on a fixed grid is problematic.
Because of the truncature, and the fixed step
 $\Delta x$ of the grid, for little curvature, $curv(u)$ will be implicitely
wrong calculated. Indeed, in a grid, if the curvature is small, in order to 
calculate it, you should diffuse a long time. But this is impossible.
We cannot diffuse too much at step 1, if we do not want to miss the evolution
 of high curvature points.
Then, the small curvatures will be implicitly computed as equal to 0, and so we
can have $u^{n+1}=u^n$, which stops the evolution.
In other words, when $\Delta t$ tends to 0,
 the scheme tends to an equation
$$ \ut& = \vert Du \vert F( curv(u) ) \qquad \hbox{ where }
 F \hbox { is defined by : } $$
$$ F(s) = \left\{ \begin{array}{l} s \; \; \hbox{ if } s \geq \hbox{ C } \\
0 \; \; \hbox{ if } \hbox{ - C } \leq s \leq \hbox{ C } \\
s \; \; \hbox{ if } s \leq \hbox{ -C } \end{array} \right. $$ 
and $C$ is a constant depending on the grid step. So consistency is in practice not
true; there is a thresholding effect on the curvature. We refer to section 6 for the
numerical confirmation.

\skipaline



\section [ Purely morphological (curve evolution) schemes.]{ Purely morphological (curve evolution) schemes.}


\subsection [Introduction.]{Introduction.}

\rm For any discretized function $u$, define its level set of value $a$ as the set of points 
$$ X_a=\{x \in \real^2 ; u(x)\geq a\} $$
We divide the datum image $u$ into a set of level sets $S$. 
Purely morphological schemes will handle directly the boundaries of the elements of $S$ which are themselves
unions of Jordan curves.

\subsection [Quasilinear intrinsic diffusion schemes.]{Quasilinear intrinsic diffusion schemes.}

 We shall first discuss
a finite element scheme for equations (2) and (5) based on Mokhtarian, Mackworth's theoretical scheme.
 Let us recall the idea of these authors for analyzing a curve.
We extract a level curve of the image, and it can be represented by a 
parametric curve 
$ C(s) = (x(s),y(s)) $ where $s$ is either the parametrization by arc length or the 
parametrization by affine length.


\rm Equation (2) and (5) are equivalent to 
\fb& \label{m4}
\frac{\partial x}{\partial t}\;  = \; \frac{\partial^2 x}{\partial s^2}
\fe&
\fb& \label{m5}
\frac{\partial y}{\partial t}\;  = \; \frac{\partial^2 y}{\partial s^2}
\fe&
Thus, the equation can be interpreted as an oriented diffusion and 
we are now ready to display a scheme, inspired from [MaMo] and [BSS]. 

\skipaline

{\bf Step 0} 
 We extract the level curves of the picture and parametrize them by length. We obtain $(x(s),y(s))$.

\skipaline

{\bf Step 1}
 We solve the equations (\ref{m4}, \ref{m5}) for a little step $\Delta t$, by convolving the
functions $x(s)$ and $y(s)$ with a gaussian function.

\skipaline

\noindent After processing, we reconstruct the image by superposing the level sets at scale t.

\underbar{So, we have here a theoretical scheme which satisfies}
\underbar {all invariants except}  \MONO .


\skipaline


\rm Let us discretize this theoretical scheme in the case of equation (2).
We start with a finite element representation of the curve to analyze,
$\tilde C^n(i)$, $i=1$,...,$N$. The affine parametrization is given by having the 
"affine length" $m_i$ of the interval $(\tilde C^n(i),\tilde C^n(i+1))$, defined by
$$m_i=\vert area[\tilde C^n(i-1),\tilde C^n(i),\tilde C^n(i+1),\tilde C^n(i+2)]\vert ^{1/3}$$ where the area is computed
algebraically by $$area(a,b,c,d)=det(b-a,c-a)+det(c-a,d-a)$$
We obtain a reparametrization of $\tilde C^n$ by affine length as
$$C^n(\sum_{j=1}^{i}m_j)=\tilde C^n(i)$$
$C^n$ is defined on $[0,\sum_{j=1}^{i}m_j]$ by affine interpolation.
Then, as in the theoretical scheme, we define the $\tilde C^{n+1}$ from $C^n$ by 
a convolution with a positive kernel (this corresponds to the computation
 of some barycenter). For simplicity, we can
take as kernel the weighted characteristic function $\frac {1}{2\epsilon}1_{[-\epsilon,\epsilon]}$
of the interval $[-\epsilon, \epsilon]$.
Indeed $\tilde C^{n+1}$ appears as the set of barycenters of "chord sets" of $C^n$.
We call {\it chord set} a set enclosed on the one side by a chord of the curve and on the other by the curve.
Roughly speaking, the preceding scheme computes a serie of chord sets with constant
area $\Delta t$ and takes their barycenters as a new polygon. It is intuitively 
true that the inf (resp the sup) is attained in the Lasry-Morel alternate scheme (iii) when the convex set
in consideration is nearby a chord set (of course, if $\Delta t$ is small enough).
 Let us now discuss the properties of our scheme. The first one to take
 in consideration is the fact that it is fully {\it affine
invariant}, because if $\vert detA \vert=1$ then the definition of $m_i$ and of
the barycenter is not affected by a change of $C$ into $A(C)$.

\skipaline



Now, we are facing a dilemma when we want to achieve full {\it scale invariance}
(i.e. when $\vert detA\vert \neq 1$). Indeed, we can achieve it by assuming that
the affine parametrization of any curve runs between 0 an 1 (Normalization of affine length)
and convolving it with a fixed kernel. In this case, we get a {\it full affine invariance};
This opens the possibility of successful multiscale shape recognition.
Now, this renormalization of affine length changes the equation: an easy
calculation shows that in this case, $T^{n\Delta t}$ should converge, when $n\Delta t$ tends to $t$,
towards the solution of 
$$\frac {\partial C}{\partial t}=\vert Length(C(t))\vert ^2 C_{ss}$$
Thus, assuming we want to analyze simultaneously several curves (which is the case
of image processing! ) we face a problem of {\it resynchronization}.
This can be done by returning to an universal time $\tau$, defined by:
$$\frac {d\tau}{dt}=(Length(C(t))^2$$
However, discretization of this last equation may in practice lead to errors in the resynchronization
(then, scale invariance would be violated because each curve is correctly analysed, no 
matter its scale, but we loose accuracy on its time-scale). The other face of the dilemma
is to give up perfect scale invariance: we convolve with a fixed kernel
the affine curve C parametrized on the interval $[0,Length(C)]$. Therefore,
we keep affine invariance, but loose scale invariance because, for instance, 
the analysis of the curve $C/2$ will be rougher than the analysis of $C$. This must be
taken into account in shape recognition tasks. We conjecture, in this last case,
that the scheme converges strongly to the solution $C(t)$ of the equation (2).
In any case we shall see that the "desynchronized scheme" is excellent in experiments.

\skipaline

\subsection [A geometrical curve evolution scheme.]{ A geometrical curve evolution scheme.}

\subsubsection [Curve sampling problems.]{ Curve sampling problems.}

We have seen that the preceding scheme changes time when the affine length of the curve changes. This problem is enhanced by the unstability of the affine length of a polygon when the discretization changes. Take as an example the case where the polygon is a square. The affine length of a square (and in general, of a polygon) is zero. If we discretize the square as discussed above, with constant euclidian step $\epsilon$, it is easily seen (see figure below) that the affine length
of the square is proportional to $\epsilon ^{2/3}$ ( $\epsilon ^2$ corresponds
to the surface of the triangles allowing the computation of the area yielding the affine length). Thus, the affine length of the square can be any value between $0$ and its area to the power $2/3$. So, there is a high dependence on the number of points involved in the discretization. (Of course, the dependence 
is also  in the position of the points). In conclusion, all invariance properties are true if the sampling has been defined in an unambiguous way. But this is impossible in practice.

\begin{figure} [htb]
  \insertps{carre.ps} {50mm}{30mm}
\end{figure}

The same problem arises in a more acute way in the scheme defined by
Bruckstein, Sapiro, Shaked [BSS]. They define the affine length of a polygon
as the number of vertices and iterate a convolution kernel on that. Therefore, it is a Mackworth-Mockhtarian scheme.

\subsubsection [A geometrical scheme.]{A geometrical scheme.}

In order to avoid the above discussed problems of sampling and synchronization,
we shall define an easy to implement version of the alternate scheme (iii) of
section 4.1.

\skipaline

Let $C^0$ be a Jordan curve, $X^0$ the set enclosed by this Jordan curve, and $x$ a point of $C^0=\partial X^0$.
Let $K_t$ be an affine invariant and translation invariant set of convex sets (e.g. all ellipses,...) with area equal to $t^{3/2}$. Then, we
define the $t$-affine opening $O_tX^0$ as the set of the barycenters of the elements of $K_t$ contained in $X^0$.
In the same way, we define the closing $F_tX^0$ as the complementary of the opening of $X^c$. And we consider the alternate scheme
$$X^{n+1/2}=O_tX^n$$
$$X^{n+1}=F_tX^{n+1/2}$$
This is the set evolution scheme associated with the convergent image evolution scheme 4.1.(iii).

\skipaline

We shall now define a practical scheme associated with this theoretical scheme.
For that, we notice that in order to define the opening, we can restrict the sets in $K_t$ to be {\it chord sets}, that is, sets bounded on the one side by the boundary and on the other by a chord. This leads to a computationally easier variant. $X$ is a set enclosed by a Jordan curve $C(s)$,
let $(C(s_0),C(s_1))$ be a ``chord", that is, a segment joining two points of $C$ with $s_0 < s_1$.

\skipaline

We define the $\Delta t$-opening as follows. For every $s_0$, we consider the chords $(C(s_0),C(s))$ and we call $A(s)$ the area of $X$ between the chord and the curve $C(\sigma )$ for $s_0 \le \sigma \le s$. The function $A(s)$ is nondecreasing and we take $s_1=\sup \{s , A(s)\le \Delta t^{3/2} \} $. We call $CH(s_0)$ the chord set associated with the chord $(C(s_0),C(s_1))$. It has an area less or equal than $\Delta t^{3/2}$.

\skipaline

Then the $\Delta t$-opening of $X$ is defined by $$O_{\Delta t}X=X\setminus (\cup_s CH(s))$$
In the same way, we can define the closing $F_{\Delta t}X$,
 by $F_{\Delta t}X=(O_{\Delta t}X^c)^c$.
Of course, $O_{\Delta t}X$ may be no Jordan set. Now, if we discretize $X$ and $C$, we can ensure that $O_{\Delta t}X$ remains a finite union of Jordan sets. We now define a practical algorithm based on the same principle.

\skipaline


1) $C(i)$ $i=1 \cdots N$ is a polygon curve enclosing $X$.

\skipaline

2) For every $i$, we find the last $j$ such that the area of the chord set $CH(C(i),C(j))$ is less than $\Delta t^{3/2}$. Then, we define a new vertex $\tilde C(i)$, contained in the vertex $(C(j),C(j+1))$. $\tilde C(i)$ is chosen so that either $\tilde C(i)=C(j)$ or the area of the chord set associated with the chord $(C(i),\tilde C(i))$ is $\Delta t^{3/2}$. Denote $CH(C(i),\tilde C(i))$ this chord set.

\skipaline

\begin{figure} [htb]
  \insertps{polygone.ps} {50mm}{30mm}
\end{figure}



The new polygon $O_{\Delta t}C$ is defined as $$O_{\Delta t}X=X\setminus (\cup_i CH(C(i),\tilde C(i))$$
It is a polygon or a union of polygons. Of course, the algorithm for computing 
$O_{\Delta t}X$ is complex if $\Delta t$ is large, but very simple if $\Delta t$ is of the same order as the distance between two consecutive vertices.

We notice that such a method is ``selfsampling" since the number of vertices cannot increase. The final algorithm consists in alternating $O_{\Delta t}$
and $F_{\Delta t}$ as explained at the beginning of this section.


\section [Experimental results.]{ Experimental results.}

\skipaline

In order to decide which schemes are invariant and robust enough for shape
 analysis and which is best, we shall simply run them on the same test images
 (with both simple invariant and complex shapes) and check all invariance
 properties askable for shape analysis.   We aim at very reliable algorithms
 and {\it cross-validation} of algorithms with very different principles is a key
 to be completely sure : so we shall match the best invariants algorithms on
 complex shapes.

 Our plan follows the plan of the preceding sections.
  We shall test in order two finite difference schemes
 (Alvarez, Alvarez-Guichard), a set evolution scheme (Merriman-Bence-Osher)
 and finally the curve evolution schemes which make a synthesis of Sapiro-Tannenbaum, Mackworth-Mocktarian and Lasry-Morel ideas.

\subsection [ The Alvarez anisotropic diffusion scheme.]{ The Alvarez anisotropic diffusion scheme.}

   We first discussed a nonconsistent stable finite difference scheme,
 based on the diffusive interpretation of equation (3).  We shall get rid
 immediately of the code, because, while it is the only one of the finite
 difference schemes to satisfy \STAB its lack of rotational invariance
 tends to transform a circular shape into a polygon, as it is clearly seen in
 figure {\it Spiral.img}. Furthermore, long range diffusion effects can be clearly
 seen on the same image and can be related to the nonconsistency of the scheme
 and has a poor behaviour when fronts are present in the image.
Therefore, this code, which is quite useful for image denoising (cf. [ALM])
 is not suitable for shape analysis : it creates shape elements which did not
 exist, and is therefore not "causal" in the sense discussed in section 2.  

\skipaline

\subsection [The Alvarez-Guichard rotationally invariant finite difference scheme.]{ The Alvarez-Guichard rotationally invariant finite difference scheme.}

Let us now test the almost fully rotationally invariant code of
 Alvarez-Guichard.  To summarize its theoretical properties, this code is
 consistent but not order-preserving nor $L^{\infty}$ stable.  We shall check
 one by one all desirable properties on test images.  

\skipaline

\begin {itemize}

\item A disk remains a disk ({\it basic principle}) : see figure ({\it Disque.img}), where a
 strong diffusion effect is also manifest.

\skipaline

\item {\it Affine invariance.}  We test it by generating a shape and its images by linear
 maps B with respective eigenvalues (1/2, 2), (1/3, 3) and (1/4, 4).
  The determinants of these maps being 1, commutation between analysis and B
 should be verified at any scale.  We display in the figure helice.img the
 corresponding experimental results.  First quadrant of ({\it helice.img}) :
 the above mentionned anamorphosis applied to the last shape on the right.
  Quadrant 2 : these shapes are analysed at some medium scale.  Quadrants 3
 and 4 : the inverse anamorphosis is applied to the original shapes as well
 as to the analyzed shapes.  Theoretically, all original shapes should be
 identical (and they are close to it, except for some
 perceptible grid effect).  The analysed shapes should also be identical
 and they are similar in size and main features, but some (important)
 inflexion points are lost.  This is due to the fact that the shapes are
 small and thin, and therefore the diffusive effect implies that some
 information is lost.  In any case, we are tempted to consider this experiment
 as positive.  

\skipaline

\item {\it Local shape inclusion.}  It is tested in the figure ({\it Cygne.img}), where two
 shapes are enclosed in each other, the interior one being oscillating.
  One sees that the inclusion of shapes is quite well verified at any scale
 until the smaller one disappears.

\skipaline

\item {\it Pure morphology}.  In principle, connected components of level sets should
 not interact.  In this figure, however, imitated from Kanisza's book La
 grammatica del vedere [Ka], we see how three of the black squares, which are
 close to each other, get into contact by a diffusion effect and create at
  large scale a "grey bean" which is clearly an artefact. This bad phenomenon,
 however, implies more a limit in accuracy of the algorithm as a true
 invalidation.

\end{itemize}

\skipaline


\subsection ["Morphologization" of the Alvarez-Guichard scheme.]{ "Morphologization" of the Alvarez-Guichard scheme.}

\rm We know that the [morphology] property can be restored by using the 
"morphological school" idea of running the algorithm separately on each level
 set of the image and then reconstructing it.  Moreover, a very efficient
 numerical idea of Osher and Sethian [OsSe] is to run the algorithm not on a set,
 but on some Lipschitz function having this set as a level set, therefore
 allowing a good behaviour of numerical schemes by avoiding explicit front
 tracking.  Let us now make some tests on simple sets.  We can first check
 again the affine invariance by noting (fig. {\it ellipsemorpho.img}) that an
 ellipse remains an ellipse with the same excentricity, when we run the
 algorithm on the distance function, and a circle remains a circle 
(figure {\it disque.img}). See also fig. {\it Muller.img}.  

{\it Morphology and scale invariance.}  Let us make another experiment
 to check wether the evolution of  a set is not altered when we run it with
two different Lipschitz functions.  In figure ({\it Cspire. img}), we run on a 
function whose value is 0 on the spiral and 10 outside.  This function has
 roughly speaking a gradient less or equal than 10.  In figure ({\it spire.img}),
 we run on  a function whose value is 0 on the spiral and 255 elsewhere.
  Thus the Lipschitz constant is 255.  Both above mentionned figures display
 the evolution of the spiral at the same number of iterations, extracted as
 the 5 level set of the first function and as the 128 level set of the second.
  One sees that the evolution of the shape and its final position short before
 disappearance are close to identical! 

 \skipaline

\subsection  [Set morphology on a grid.]{ Set morphology on a grid.}

\rm Here, theory and experimentation diverge : as explained above,
 Merriman, Bence and Osher conjectured  that a particular iterated median filter
 converges towards the mean curvature motion while computer vision researchers know  
 quite well that a median filter, iterated on a grid, remains steady after
 some iterations.  We display in figure ({\it planchetriangle.img}) the result of
 these iterations of the Merriman-Bence-Osher scheme on both a noisy binary
 image (above) and a grey level noisy image (below).  The good denoising
 result is certainly imputable to the mean curvature effect (elimination of 
high curvature).  Now, medium and low curvature simply remain steady in the
 right figures.  In these figures, one can look at the smoothed corners of 
the triangle and rectangle : they correspond to pieces of disks with a radius
 of five pixels ; roughly speaking the size of the support of the used Gauss
 function...  If we wanted to smooth further the shapes, we should enlarge 
the gaussian until its support exceeds by much the size of the picture.  But
 then, the analysis would of course loose any local character...  We think
 that no good simple solution can be given to this problem if we keep the grid
 discretization of the analysed sets.  So we pass to curve evolution schemes,
 which allow an arbitrary accuracy on the position of the curves and therefore
 of their curvature and speed.

\skipaline


\subsection [Purely morphological (curve evolution) scheme.]{ Purely morphological (curve evolution) scheme.}

\skipaline

Here again, we check all invariance properties. As a matter of fact, both above defined curve evolution schemes behave in exactly the same way and we shall comment them jointly.

\skipaline

\begin{itemize}

\item {\it Shape inclusion principle} : Figure ({\it planchecygne}).
 Notice how close this evolution is to the Alvarez-Guichard scheme.

\skipaline

\item {\it Local shape inclusion principle} : Figure ({\it plancherosace}).  This principle
 is not theoretically true for the algorithm.  In pratice, it seems to be
 quite well true.

\skipaline

\item {\it Affine invariance} :   Figure ({\it plancheellipse}). An ellipse remains
 an ellipse with the same excentricity. Figures ({\it plancheaffine}) and 
 ({\it planchereconstruite}) : we repeat the same experiment as in the case of 
the Alvarez-Guichard code.  The affine invariance result is almost perfect.

\skipaline

\item {\it Scale invariance}.   The algorithm (in its "desynchronized" version), has been
 written to be perfectly scale invariant.   If we dilate a polygonal shape 
(that is, an array of points with floating point coordinates) by any floating
 point matrix, then the discretized affine parameter, the convolution, etc...
 will be computed in exactly the same way with the same samplings, etc... So the
 algorithm yields experimentally and in practice exactly the same results. 
 The only problem could arise from "resynchronization" between different 
curves.  We can look again at ({\it planchereconstruite}) to check how well this
 resynchronization works.  If we look at the "blobs" of the last quadrant,
 we see that three of them are identical and one is slightly bigger. 
 This difference comes from a grid effect, the anamorphosis having increased
the area of the initial fourth shape.  This was not perceptible at small or
 medium scale, but is at larger scale because the multiscale analysis tends
 to sharpen the size differences of shapes.  In any case, we conclude to an
 almost perfect scale invariance after resynchronization.

\end{itemize}

\skipaline

\noindent {\bf Crossvalidation of the "best schemes".}
This crossvalidation can be made in a very simple way. 
 Indeed, the theoretical times in both algorihms are proportional
 and we can make them in practice very close by "calibrating" the time
 so that a circle with radius $t$ disappears in time $t$.  Then, crossvalidation
 consists in running both algorithms at exactly the same times on a complex 
shape.  The spiral is well adapted, because it has a mix of high and very 
small curvature and lives a long time before disappearing.  The figure
 ({\it planchespirale}) displays the evolution of the spiral at exactly the same
 times as in the figures ({\it spire.img}) and ({\it Cspire.img}).  Crossvalidation is clear.

\skipaline

\section [Conclusion and conjectures.] {Conclusion and conjectures.}

\skipaline

  We have defined and discussed in this paper several numerical schemes for
 the fundamental equation of image processing.  Since the equation is new,
 the schemes are also new but we took the occasion to match for a first time
 numerical ideas with very different origins (finite difference schemes, mathematical
 morphology, multiscale shape analysis theory...).  We also checked sharp
 consistency criteria, based on invariance.

Among the discussed schemes, two appear as very reliable because of their 
cross-validation : a consistent classical finite differences scheme and an
 adaptive finite element curve evolution scheme, with nonlocal aspects.  
The second is, however, almost perfect from the shape analysis viewpoint : 
it preserves accurately the invariance properties of the fundamental equation
 on very long times.  Of course, its use for complex image analysis will lead 
to run it on an huge number of curves, but this seems feasible with the actual
 technology.  For many tasks in image analysis, the first scheme is reliable
 enough.

\skipaline

Let us finish by stating how the preceding schemes could be mathematically
 proved to converge.  For the finite difference scheme, there is not much hope
 because it is not order preserving and therefore a formal convergence proof 
towards the viscosity solution is problematic.  We conjecture that the curve
 evolution schemes converge (e.g. for the Hausdorff distance) towards the 
exact evolution of any initial Jordan curve with finite length.  Because of
 the lack of a shape inclusion principle for the fully discretized scheme, it seems however
 advisable to restrict this conjecture to the semidiscretized schemes (i),
 to (iv), because those schemes verify all four invariance and order 
preserving principles stated in section 2.  Since we know that those 
principles can only lead to the fundamental equation (and its "affine 
opening" and "affine closing" variants), the conjecture seems to be more
 than sound.

\newpage

 
\input{appen.tex}

\newpage

\input{fignum/planche.tex}


\newpage

{\bf References}

\skipaline

[AGLM1] L. Alvarez, F. Guichard, P.L. Lions and J.M. Morel. Axiomes et \'equations fondamentales
du traitement d'images. Report 9216, CEREMADE. Universit\'e Paris Dauphine, 1992.
Accepted at Arch. for Rat. Mech., July 1992.

\skipaline


[AGLM2] L. Alvarez, F. Guichard, P.L. Lions and J.M. Morel. 
Axiomatisation et nouveaux op\'erateurs de la morphologie math\'ematique.
C.R. Acad. Sci. Paris, t.315, Serie I, p. 265-268, 1992.

\skipaline


[AhSc]  N. Ahuja and B. Schachter.     Pattern Models,  Wiley, New York 1983.

\skipaline


[AlGu] L. Alvarez, F. Guichard. Software MEGAWAVE, user's guide of the mean curvature motion package.

\skipaline


[ALM] L. Alvarez, P.L. Lions and J.M. Morel. Image selective smoothing and edge
 detection by nonlinear diffusion (II). SIAM Journal of numerical analysis 29, pp 845-866. 1992.

\skipaline


[Ang] S. Angenent. Parabolic equations for curves on surfaces I, II. University of
 Wisconsin-Madison. Technical Summary Reports, 89-19, 89-24, 1989.

\skipaline


[AsBr] H. Asada and M.Brady. The curvature primal sketch. IEEE Transactions on Pattern analysis and machine intelligence,  Vol. 8, No. 1, January. 1986.

\skipaline


[Bar] G. Barles. Remarks on a flame propagation model. Technical Report No 464 INRIA Rapports de Recherche, December 1985.

\skipaline


[BaGe] G. Barles and C. Georgelin. A simple proof of convergence for an approximation
scheme for computing motions by mean curvature. Preprint 1992.

\skipaline


[BaSo]  G. Barles and P.E. Souganidis. Convergence of approximation schemes for fully nonlinear second order equation, Asymp. Anal., to appear.

\skipaline


[BPH]  E.B.Barret, P.M.Payton, N.N.Haag and M.H.Brill.
 General methods for determining projective invariants in imagery.
 Computer Vision Graphics Image Proc. Jan. 1991.

\skipaline


[Bre]  H. Brezis.     Analyse Fonctionnelle, Th\'eorie et Applications.  Masson, Paris, 1987.

\skipaline


[BSS] A.M. Bruckstein, G. Sapiro and D. Shaked. Affine-invariant evolutions of planar polygons. Preprint June 1992.

\skipaline


[CCLM]   F. Catte, T. Coll, P.L. Lions and J.M. Morel.    Image selective smoothing and edge detection by nonlinear diffusion.     Preprint, CEREMADE 1990.  To appear in SIAM Journal of Numerical Analysis.

\skipaline


[CGG]  Y-G. Chen, Y. Giga and S. Goto.      Uniqueness and existence of viscosity solutions of generalized mean curvature flow equations, Preprint, Hokkaido University, 1989.

\skipaline


[CGHH]  Y-G. Chen, Y. Giga, T. Hitaka and M.Honma : Numerical analysis of motion of a surface by its mean curvature. Preprint, Hokkaido University.

\skipaline


[CIL]   M.G. Crandall, H.  Ishii and P.L. Lions.     User's guide to viscosity solution of second order partial differential equation.  Preprint, CEREMADE, 1990.

\skipaline


[CrLi] M.G. Crandall and P.L. Lions. Personal communication.

\skipaline


[Dia]  J.I. Diaz.     A nonlinear parabolic equation arising in image processing.   Extracta Matematicae, Universidad de Extremadura 1990.

\skipaline


[DuTs] G. Dubek and John Tsotsos. Recognising planar curves using curvature-tuned smoothing. Third Conference on computer vision 1990. IEEE computer Society Press.

\skipaline


[Eva] G. Evans. Convergence of an algorithm for the mean curvature. Preprint 1992.

\skipaline


[EvSp]  L.C. Evans and J. Spruck.      Motion of level sets by mean curvature, I., preprint.

\skipaline


[FMZ] D.Forsyth, J.L.Mundy, A.Zisserman, C.Coelho, A.Heller and C.Rothwell.
 Invariant descriptors for 3D object recognition and Pose.
 IEEE Transaction of pattern analysis and machine intelligence.
 Vol 13 N.10 1991.

\skipaline


[Gab]  D. Gabor.     Theory of communication.     J. Inst. Elect. Engr. 93, 429-457, 1946.

\skipaline


[GaHa] M. Gage and R.S. Hamilton. The heat equation shrinking convex plane curves.
J. Differential Geometry 23, pp. 69-96, 1986.

\skipaline


[GGIS]  Y. Giga, S. Goto, H. Ishii and M.-H. Sato.     Comparison principle and convexity preserving properties for singular degenerate parabolic equation on unbounded domains.  Preprint, Hokkaido University, 1990.

\skipaline


[GiGo]  Y. Giga and  S. Goto. Motion of hypersurfaces and geometric equations. J. Math. Soc. Japan, Vol. 44, No. 1, 1992.

\skipaline


[GKW] G.H. Granlund, H. Knutsson and  R. Wilson.
 Anisotropic non stationary image and its applications.
 Picture Processing Laboratory, Linkoeping University S581 83 Linkoeping, Sweden.

\skipaline


[Gray] M. Grayson. The heat equation shrinks embedded plane curves to round points.
 J. Differential Geometry 26, pp. 285-314, 1987.

\skipaline


[Hart]  R.Hartshorne. Foundations of Projective Geometry.  Benjamin, 1967.

\skipaline


[HoNo]  K. Hollig and J.A. Nohel.     A diffusion equation with a nonmonotone constitutive function.     Proc. on Systems of Nonlinear Partial Differential Equations, John Ball ed., pp 409-422, Reidel 1983.

\skipaline


[Hum] R. Hummel. Representations based on zero-crossings in scale-space.
Proc. IEEE Computer Vision and Pattern Recognition Conference, pp. 204-209, 1986.

\skipaline


[Ka] G. Kanisza. La grammatica del Vedere, Il Mulino, Bologna 1980.

\skipaline


[Kim] B.B. Kimia. Toward a computational theory of shape. Ph. D. Dissertation, 
Department of Electrical Engineering, McGill University, Montreal, Canada, August 1990.

\skipaline


[KoDo]   J.J. Koenderink and A.J. van Doorn. Dynamic shape. Biol. Cyber.,53:383-396, 1986.

\skipaline

 
[Koe1]   J.J. Koenderink.     The structure of images, Biol. Cybern.  50, 363-370, 1984.

\skipaline

 
[Koe2]   J.J. Koenderink. Solid Shape. MIT Press, Cambridge, MA 1990.

\skipaline


[Koeh] W. Koehler.      Psychologie de la forme.  Id\'ees nrf-Gallimard, 1964.

\skipaline


[KTZ] B.B. Kimia, A. Tannenbaum, and S.W. Zucker. On the evolution of curves via a function
of curvature, 1: the classical case. J. of Math. Analysis and Applications. Vol. 163, No 2, Jan. 15 1992.

\skipaline


[LaMo] J.M. Lasry and J.M. Morel. A monotone consistent theoretical scheme for the
fundamental equation of image processing. preprint.

\skipaline



[Lio]   P.L. Lions.   Generalized solutions of Hamilton-Jacobi equations,  Research notes in Mathematics, 69, Pitman Boston 1982.

\skipaline


[LiSr] H-C. Liu and M. D. Srinath  Partial Shape Classification Using Contour Matching in Distance Transformation.  IEEE Transactions on Pattern analysis and machine intelligence,  Vol. 12, No. 11, Nov. 1990.

\skipaline


[LoMo] C. Lopez, J.M. Morel. 
Axiomatisation of shape analysis and application to texture hyperdiscrimination.
Proceedings of the Trento Conference on Surface Tension and Movement by Mean Curvature. De Gruyter Publishers. Berlin 1992.

\skipaline


[LSU]  O.A. Ladyzhenskaja, V.A. Solonnikov and N.N. Ural'tseva.
Linear and quasilinear equation of parabolic type.
American Mathematical Society, Providence, R.I. 1968.

\skipaline


[LSW]  Y.Lamdan, J.T.Schwartz and H.J.Wolfson. Object recognition by affine invariant matching. In Proc. CVPR 88, 1988.

\skipaline


[MaHi] D. Marr and E. Hildreth,     Theory of edge detection.   Proc. Roy. Soc. Lond. B207  1980, 187-217.

\skipaline


[MaMo1] A. Mackworth and F.Mokhtarian. Scale-Based description and recognition of planar curves and two-dimensional shapes.  IEEE Transactions on Pattern analysis and machine intelligence,  Vol. 8, No. 1, January. 1986.

\skipaline


[MaMo2] A. Mackworth and F.Mokhtarian. A theory of multiscale, curvature-based shape 
representation for planar curves. IEEE Trans. Pattern Anal. Machine Intell. 14, pp 789-805, 1992.

\skipaline


[MaPe]  J.Malik and P. Perona.     A computational model of texture perception.   Preprint UCB/CSD 89/491, Dept of Electrical Engineering and Computer Sciences, Univ. of California  Berkeley 1989.

\skipaline


[Mara1] P. Maragos : tutorial on advances in morphological image processing and analysis. optical engineering, july 1987, Vol. 26 No. 7.

\skipaline


[Mara2] P. Maragos. Pattern spectrum and multiscale shape representation. PAMI, 11(7):701-716, july 1989.

\skipaline


[Marr1] D. Marr    Vision.   Freeman and Co. 1982.

\skipaline


[Masc] P. Mascarenhas. Diffusion generated motion by mean curvature. Preprint 1992.

\skipaline


[MBO] B. Merriman, J. Bence, S. Osher. Diffusion Generated motion by Mean Curvature.
April 1992. CAM Report 92-18. Depart. of Mathematics. University of California, 
Los Angeles CA. 90024.1555.

\skipaline


[NiSh]  M. Nitzberg and Takahiro Shiota.     Nonlinear Image Smoothing with Edge and Corner Enhancement.   Technical Report n¡ 90-2,  Division of Applied Sciences, Harvard University, Cambridge, MA 01238, 1990.

\skipaline


[Nor]  K. N. Nordstrom.     Biased anisotropic diffusion- A unified Approach to Edge Detection.  Preprint.  Dept. of Electrical Engineering and Computer Sciences, University of California, Berkeley, CA 94720.  (1989).

\skipaline


[OsRu]  S. Osher and L. Rudin,     Feature-oriented image enhancement using shock filters.    SIAM J. on Numerical Analysis, to appear.

\skipaline


[OsSe]   S. Osher and J. Sethian.     Fronts propagating with curvature dependent speed : algorithms based on the Hamilton-Jacobi formulation.   J. Comp. Physics, 79, 12-49, 1988.

\skipaline


[PeMa]  P. Perona and J. Malik.  Scale space and edge detection using anisotropic diffusion.   Proc. IEEE Computer Soc.  Workshop on Computer Vision, 1987.

\skipaline


[RaCh] A. Rattarangsi and R. T. Chin.   Scale-Based Detection of Corners of Planar Curves.  Third Conference on computer vision 1990. IEEE computer Society Press.

\skipaline


[RoTh]  A. Rosenfeld and M. Thurston.     Edge and curve detection for visual scene analysis.    IEEE Trans. on Computers, C-20, 562-569, May 1971.

\skipaline


[SaTa1] G. Sapiro and A. Tannenbaum. On affine plane curve evolution. Department of
 electrical engineering. Technion Israel Institute of Technology. Haifa. Israel. EE Pub 821. February 1992, submitted.

\skipaline

  
[SaTa2] G. Sapiro and A. Tannenbaum. Affine shortening of non-convex plane curves . Department of
 electrical engineering. Technion Israel Institute of Technology. Haifa. Israel. EE Pub 845. February 1992, submitted.

\skipaline

  
[Ser] J. Serra  Image analysis and mathematical morphology, Vol 1. Academic Press 1982.

\skipaline


[SiGi] D. Sinha and C.R.Giardina. Discrete black and white object Recognition via morphological functions. IEEE Transactions on Pattern analysis and machine intelligence,  Vol. 12, No. 3, March 1990.

\skipaline


[SMCM] P. Saint-Marc, J.-S. Chen, and G. Medioni  Adaptative Smoothing: A General Tool for Early Vision.  IEEE Transactions on Pattern analysis and machine intelligence,  Vol. 13, No. 6, June 1991.

\skipaline


[Son]  M. Soner.     Motion of a set by the curvature of its mean boundary.   Preprint.

\skipaline


[Wei]  I.Weiss. Projective invariants of shapes. In Proc. DARPA IU Workshop, 1989, pp 1125-1134.

\skipaline


[Wer] M. Wertheimer.     Untersuchungen zur Lehre von der Gestalt II, Psychologische Forschung, 4, 301-350, 1923.


\skipaline


[Wit]  Witkin, A. P.   Scale-space filtering.     Proc. of IJCAI, Karlsruhe 1983, 1019-1021.

\skipaline


[YuPo]  A. Yuille and T. Poggio.     Scaling theorems for zero crossings.     IEEE Transactions on Pattern Analysis and Machine Intelligence, 8, January 1986. 

\skipaline


[Yui] A. Yuille. The creation of structure in dynamic shape. Proc. of the second international conference on computer vision, Tampa 1988, pp. 685-689.


