%gmChap12.tex.

\graphicspath{{./figures/}}

\chapter{Affine-Invariant Mathematical Morphology\label{ChapAffineInvariantMathMorpho}}

In Chapter \ref{Chap8}, we introduced  a class of simple set and
function operators called erosions and dilations. These operators
were defined by a single structuring set. They are contrast
invariant and translation invariant, but they are not affine
invariant. In this chapter, we introduce set operators, also
called erosions and dilations, that are affine invariant.

Our interest in affine-invariant  smoothing, like our interest in contrast- and translation-invariant smoothing, is
based on practical considerations. When we take a photograph of a plane image, say, a painting, the image is projected
onto the focal plane of the camera. If the camera is an ideal pin-hole device, then this is a projective transformation
where the center of projection is the pin hole. In any case, it approximates a projective transformation. If we are far
removed from the plane of the painting, then the focal plane of the camera approximates the plane at infinity, and the
transformation looks like an affine transformation. For a more common example, we note that most digital cameras, copy
machines, fax machines, and scanners introduce a slight affine distortion. Thus, we would like the smoothing to be
affine invariant so it is ``blind'' to any deformations introduced by these processes. It would be nice to have a
smoothing that is invariant under the full projective group, but we will see later (Chapter \ref{Chap18}) that this is
not possible.

\section{Affine invariance}

Isometries, by definition, preserve  the distance between points, and hence, preserve the angle between vectors. In a
finite dimensional space $\RR^N$, any isometry can be represented by $\fxx\mapsto A\fxx+\fxa$, where $A$ is an
orthogonal matrix and $\fxa$ is a fixed vector. These transformations include all of the rigid motions of $\RR^N$ plus
reflections. Classical Euclidean geometry in $\RR^2$ is concerned with the objects that are invariant under these
transformations. If we loosen the requirement that the matrix $A$ be orthogonal and assume only that it is nonsingular,
then we have generalized Euclidean motions to affine motions, and the distance between points is no longer an
invariant. However, there are affine invariants, and the most important from our point of view is that parallel lines
are mapped into parallel lines and finite points are mapped into finite points. Furthermore, if the determinant of $A$
is one, $|A|=1$, then the transformation preserves area: Unit squares are mapped into parallelograms whose area is one.
Note, however, that the parallelograms can be arbitrarily long.

If we jump to projective geometry and  the projective plane, then parallel lines are not necessarily preserved.  Thus,
affine transformations are a special class of  projective transformations. This means that affine geometry can be
considered a generalization of Euclidian geometry or a specialization of projective geometry. Incidentally, this is the
view taken in classical Chinese drawing, which tends always to display scenes as seen from a distance and to maintain
parallelism.


\begin{figure}[!t]
\setkeys{Gin}{width=12cm} \centerline{
\includegraphics{Perspective.eps}
} \caption[Perspective view]{A rectangle seen from far enough has its sides roughly parallel and looks like a
parallelogram. Thus affine invariance is a particular instance of projective invariance.} \label{figure_chord_arc_min}
\end{figure}
\section{Affine-invariant erosions and dilations}

Everything in this chapter will take place in $\RR^2$ so the
following definition is given for $\RR^2$. The group of all linear
affine transformations $A:\RR^2\to\RR^2$  with determinant one,
$|A|=1$, is called the special linear group; it is often denoted
by $SL(\RR^2)$.

Our goal is to define erosions  and dilations that are invariant
under $SL(\RR^2)$. Any attempt to do so using Euclidean distance
is doomed to failure, since the distances between points are not
affine invariant. It is thus necessary to base the definition of
affine-invariant erosions and dilations on some affine invariant,
and the most obvious one to use is area. This leads to the notion
of the \textit{affine-invariant distance} between a point and a
set. We begin with the definition of a \textit{chord-arc set}.

\begin{definition}Let $X$ be a subset
of $\;\RR^2$ and let $\Delta$ be a straight line in $\RR^2$. Any
connected component of $X\setminus\Delta=X\cap\Delta^c$ is called
a chord-arc set defined by $X$ and $\Delta$.
\end{definition}

\begin{exercise}\label{exercise12.1}Chord-arc sets  take their name from the case where $X$ is a disk, in which case
 a chord-arc set is called a segment. What are the chord-arc sets if (i) $X$ is an open disk and (ii) $X$ is a
 closed disk? What is the situation when $X$ is a closed arc of a circle or a closed segment of a disk? \finex
\end{exercise}

\begin{exercise}\label{exercise12.2}Suppose that $\fxx\in({\overline X})^c\cap\Delta$. Show that there are two,
 and only two, chord-arc sets defined by $({\overline X})^c=(X^c)^\circ$ and $\Delta$ that contain $\fxx$ in
  their boundary. (Note that we are assuming that $({\overline X})^c\not=\emptyset$.) \finex
\end{exercise}

We are interested first in some special chord-arc sets that will be used to define the affine distance from a point
$\fxx$ to a set $X$. From Exercise \ref{exercise12.2}, we know that there are only two chord-arc sets defined by
$({\overline X})^c$ and $\Delta$ that contain $\fxx$ in their boundary, if ${\overline X}\not=\RR^2$. In this case, we
call these two sets $CA_1(\fxx,\Delta,X)$ and $CA_2(\fxx,\Delta,X)$, and we order them so that
\[
{\rm area}(CA_1(\fxx,\Delta,X))\leq{\rm area}(CA_2(\fxx,\Delta,X)).
\]

\begin{definition} \label{definition12.2}
Let $X$ be a subset of $\;\RR^2$ and let $\fxx$ be an arbitrary point in $\RR^2$. We define the affine distance from
$\fxx$ to $X$ to be $$\delta(\fxx,X)=\inf_\Delta[{\rm area}(CA_1(\fxx,\Delta,X))]^{1/2} \hbox{ if }\fxx\in({\overline
X})^c \hbox{ and } \delta(\fxx,X)=0 \hbox{ otherwise.}$$ (See Figure \ref{figure_chord_arc_min}.)
\end{definition}

The power $1/2$ is taken so that $\delta$ has the ``dimension'' of a distance.   Notice that $\delta(\fxx,X)$ can be
infinite: Take $X$ convex and compact and $\fxx\not\in X$. Then all chord-arc sets defined by a straight line $\Delta$
through $\fxx$ have infinite area. Notice also that $\delta(\fxx,\emptyset)=+\infty$ and $\delta(\fxx,\RR^2)=0$.

\begin{definition}The affine a-dilation  $\tilde{\mathcal D}_a$
and the affine a-erosion $\tilde{\mathcal E}_a$ are set operators defined for $X\subset\RR^2$ by $$\tilde{\mathcal D}_a
X=\{\fxx\mid\delta(\fxx,X)\leq a^{1/2}\}\hbox{ and }\tilde{\mathcal E}_a X=\{\fxx\mid\delta(\fxx,X^c)> a^{1/2}\}.$$
They are extended to $\mathcal M(S_2)$ by the standard extension (Definition \ref{defstandardextension}.)
\end{definition}

\begin{exercise}Check that $\tilde{\mathcal D}_a\RR^2=\tilde{\mathcal E}_a\RR^2=\RR^2$. Show
that $\tilde{\mathcal E}_a X=(\tilde{\mathcal D}_a X^c)^c$. (Recall Exercise 8.1(ii).) This relation
 shows that eroding a set and dilating its complement yield complementary sets. This is a useful symmetry,
 since the same shape can appear as an upper level set or as the complement of an upper level set, depending
 on whether it is darker or lighter than the background. \finex
\end{exercise}



\begin{figure}[!t]
\setkeys{Gin}{width=10cm} \centerline{
\includegraphics{fig12.01.1.eps}
}
\caption[Affine distance to a set]{Affine distance to a set.}
\label{figure_chord_arc_min}
\end{figure}

The names we have used for the operators $\tilde{\mathcal E}_a$ and $\tilde{\mathcal D}_a$ are not standard
nomenclature in mathematical morphology. Indeed, in mathematical morphology, a dilation must commute with set union and
an erosion is expected to commute with set intersection. It is easy to check that $\tilde{\mathcal E}_a$ and
$\tilde{\mathcal D}_a$ do not satisfy these properties.\footnote{We thank Michel Schmitt for pointing this out to us.}
Nevertheless, we will use these names. There should be no confusion, and these operators are natural generalizations of
the corresponding Euclidean erosions and dilations discussed in Chapter \ref{Chap8}.

\begin{exercise} Prove the above statements, that a standard erosion commutes with set intersection,
a standard dilation commutes with set union. Give examples showing that this commutation is no more true with affine
dilation or erosion.\finex
\end{exercise}

\begin{proposition} $\tilde{\mathcal E}_a$ and $\tilde{\mathcal
D}_a$ are monotone and affine-invariant. More precisely, for every linear map $A$ such that $|A|>0$, $\tilde{\mathcal
E}_aA=A\tilde{\mathcal E}_{|A|^{-1}a}$ and $\tilde{\mathcal D}_aA=A\tilde{\mathcal D}_{|A|^{-1}a}$. In particular,
$\tilde{\mathcal E}_aA=A\tilde{\mathcal E}_{a}$ and $\tilde{\mathcal D}_aA=A\tilde{\mathcal D}_{a}$ if $|A|=1$.
\end{proposition}

\begin{proof}If $X\subset Y\subset \RR^2$, then it is easily seen from the
definitions that $\delta(\fxx,Y)\leq\delta(\fxx,X)$ for every
$\fxx\in\RR^2$. It then follows from the definition of
$\tilde{\mathcal D}_a$ that $\tilde{\mathcal
D}_aX\subset\tilde{\mathcal D}_aY$. Hence, $\tilde{\mathcal D}_a$
is monotone. The monotonicity of $\tilde{\mathcal E}_a$ follows
directly from the relation $\tilde{\mathcal E}_a
X=(\tilde{\mathcal D}_a X^c)^c$.

The transformation $A$ preserves the topological properties of the configuration determined by $\fxx$, $X$, and
$\Delta$ and multiplies all areas by $|A|$.  This implies that $\delta(A\fxx,AX)=|A|^{1/2}\delta(\fxx,X)$. It follows
from the definition of $\tilde{\mathcal D}_a$ that $\tilde{\mathcal D}_aAX=A\tilde{\mathcal D}_{|A|^{-1}a}X$. Thus
$\tilde{\mathcal D}_aA=A\tilde{\mathcal D}_{|A|^{-1}a}$. The result for $\tilde{\mathcal E}_a$ follows from the result
for $\tilde{\mathcal D}_a$ and the relations $AX^c=(AX)^c$ and $\tilde{\mathcal E}_a X=(\tilde{\mathcal D}_a X^c)^c$.
The extension of this relation to subsets of $\RR^2\cup \{\infty\}$ is straightforward, since we have set
$A\infty=\infty$.
\end{proof}

 The next proposition shows that it is equivalent to erode a set or its interior, and to dilate a set or its
 closure.

\begin{proposition}\label{proposition12.5}For any $X\subset\RR^2$,
$\tilde{\mathcal E}_aX=\tilde{\mathcal E}_aX^\circ$ and $\tilde{\mathcal D}_aX=
\tilde{\mathcal D}_a\overline{X}$, where $X^\circ$ denotes the interior of
$X$ and $\overline{X}$ denotes the closure of $X$.
\end{proposition}

\begin{proof}We will first prove the result about $\tilde{\mathcal
E}_a$. Since $\tilde{\mathcal E}_a$ is monotone, $\tilde{\mathcal
E}_aX^\circ\subset\tilde{\mathcal E}_aX$. Now,
$\fxx\in\tilde{\mathcal E}_aX$ if and only if
$\delta(\fxx,X^c)>a^{1/2}$. By the definition,
$\delta(\fxx,Y)=\delta(\fxx,\overline{Y})$, so
$\fxx\in\tilde{\mathcal E}_aX$ if and only if
$\delta(\fxx,\overline{X^c})>a^{1/2}$. Since
$\overline{X^c}=(X^\circ)^c$, this means that
$\delta(\fxx,(X^\circ)^c)>a^{1/2}$, which proves that
$\fxx\in\tilde{\mathcal E}_aX^\circ$. That $\tilde{\mathcal
D}_aX=\tilde{\mathcal D}_a\overline{X}$ follows from the two
identities $\tilde{\mathcal E}_a X=(\tilde{\mathcal D}_a X^c)^c$
and $((X^c)^\circ)^c=\overline{X}$.
\end{proof}

This result means in particular that affine erosion erases all
boundary points. It is easy to check that the affine erosion
processes independently connected components of a set. This is the
object of the next exercise.

 \begin{exercise} \label{localiteerosion}Let $X_i^\circ$, $i\in
 I$, be the
connected components of $X^\circ$. Then the $\tilde{\mathcal
E}_aX_i^\circ$ are disjoint and $\tilde{\mathcal
E}_aX^\circ=\bigcup_{i\in I} \tilde{\mathcal E}_aX_i^\circ$.
\end{exercise}

 \begin{lemma}\label{affinestandard}  $\tilde{\mathcal E}_a$ and $\tilde{\mathcal D}_a$ are standard monotone.
 \end{lemma}

\begin{proof} We have to check five properties, but the three first items of Definition \ref{defstandardmonotone}
are obvious.  Let $X\subset \RR^2$ be bounded. Then $\tilde{\mathcal E}_aX\subset X$ also is bounded. Assume now that
$X^c$ is bounded. Then $X\supset \overline{B(0,R)^c}$ for some $R\geq 0$. It is easily checked that $\tilde{\mathcal
E}_a(\overline{B(0,R)^c})=\overline{B(0,R)^c}.$ Thus $\tilde{\mathcal E}_a(X)\supset \overline{B(0,R)^c}.$  We conclude
that $\tilde{\mathcal E}_a$ is standard monotone.  By Proposition \ref{dualstandardmonotone} its dual operator
$\tilde{\mathcal D}_a$  also is standard monotone.
 \end{proof}

\begin{figure}[!t]
\setkeys{Gin}{width=12cm} \centerline{
\includegraphics{fig12.02.1.eps}
} \caption[An affine structuring element]{An affine structuring
element:  All lines through $0$ divide $B$ into several connected
components. The two of them which contain $0$ in their boundary
have area larger or equal to $b$.}
\label{figure_structuring_element}
\end{figure}

\begin{definition}\label{definition12.6} A set $B$ is called an affine structuring element if
$B$ is open and connected and if $\delta(0,B^c)>1$. We denote the set of all affine structuring elements by $\mathcal
B_{\rm aff}$. \end{definition}


\begin{exercise}
If $A$ is a linear  transformation and  $B$  an affine structuring element, check that
$\delta(0,(AB)^c)=\delta(0,AB^c)=|A|^{1/2}\delta(0,B^c)$. Deduce that $A\mathcal B_{\rm aff}=\mathcal B_{\rm aff}$ for
all $A\in SL(\RR^2)$.\finex
\end{exercise}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\[
\mathcal T X=\bigcup_{B\in\mathcal B}\bigcap_{\fxy\in B}(X-\fxy)=\{\fxx\mid\fxx+B\subset X \text{ for some }B\in\mathcal B\},
\]
where $\mathcal B=\{X\mid 0\in\mathcal TX\}$. The  task reduces to
characterizing the set of structuring elements $\mathcal B$. We
know that $0\in\tilde{\mathcal E}_aX$ if and only if
$\tilde{\mathcal E}_aX\not=\emptyset$ and $\delta(0,X^c)>a^{1/2}$,
and this, and the results stated above, lead to the following
definition.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{proposition}  $\mathcal B_1=a^\frac 12 \mathcal B_{aff}$ is a standard set of structuring elements for
$\tilde{\mathcal E}_a.$ Thus for every set $X\subset\RR^2$,
\[
\tilde{\mathcal E}_a X= \bigcup_{B\in\mathcal B_{\rm
aff}}\bigcap_{\fxy\in
a^{1/2}B}(X-\fxy)=\{\fxx\mid\fxx+a^{1/2}B\subset X \text{ for some
}B\in\mathcal B_{\rm aff}\}.
\]
\end{proposition}

\begin{proof}
$\tilde{\mathcal E}_a$ is translation invariant and standard monotone. Thus we can apply Matheron Theorem
\ref{theorem7.1}.  The canonical set of structuring elements of $\tilde{\mathcal E}_a$ is
$$\mathcal B_0=\{B\mid \tilde{\mathcal E}_a\ni 0\}=\{B\mid \delta(0, B^c)>a^\frac 12.\}.$$
Then $\mathcal B_1=a^\frac 12\mathcal B_{aff}$ is the subset of elements in $\mathcal B_0$ which are open and
connected.  By Proposition \ref{reductiondeselementstructurants} we only need to show that every element $B_0$ in
$\mathcal B_0$ contains some element $B_1$ of $\mathcal B_1$.  Let us choose for $B_1$ the open connected component of
0 in $B_0$. For every line $\Delta$ passing by 0, $CA_1(0, \Delta, B_0^c)$ is a connected open set contained in
$B_0\setminus \Delta$. Thus it is also contained in $B_1\setminus \Delta$.  This implies that $CA_1(0, \Delta,
B_1^c)\supseteq CA_1(0, \Delta, B_0^c)$ and, by taking the infimum of the areas of these sets, that $\delta(0,
B_1^c)\geq \delta (0, B_0^c)>a^\frac 12.$

\end{proof}

\begin{remark} An alternative way to prove the above proposition is the following. By Proposition \ref{proposition12.5}
and the result of Exercise \ref{localiteerosion} we know that
$$\tilde{\mathcal E}_a B_0=\tilde{\mathcal E}_a B_0^\circ=\cup_{i\in  I}\tilde{\mathcal E}_a\left[(B_0^\circ)_i\right],$$ where
$(B_0^\circ)_i $ are the open connected components of $B_0^\circ.$ Now one of them $(B_0)_i=B_1$ is the open connected
component containing 0.  Thus $\tilde{\mathcal E}_aB_0\ni 0\Leftrightarrow \tilde{\mathcal E}_aB_1\ni 0.$
\end{remark}

Let us give a more practical  characterization for the affine structuring elements, which follows immediately from
Definitions \ref{definition12.2} and \ref{definition12.6}.

\begin{proposition} A set $B$ is an affine structuring element if
it is open, connected, and contains the origin, and if for some
$b>1$ and for every straight line $\Delta$ through the origin, the
two connected components of $B\setminus\Delta$ that contain the
origin in their boundary each have area greater than some number
$b>1$. (See Figure \ref{figure_structuring_element}.)
\end{proposition}

It is easy to see that $\tilde{\mathcal E}_a$ is not upper semicontinuous on $\mathcal L$. $\tilde{\mathcal E}_a$ sends
a closed disk on an open disk and therefore doesn't map $\mathcal L$ into itself. As for $\tilde{\mathcal D}_a$, it is
not known whether it is upper semicontinuous or not and this is a good question! All the same we can define a stack
filter for $\tilde{\mathcal D}_a$ or $\tilde{\mathcal E}_a$ by the superposition principle. Thus we set for $u\in
\mathcal F$,
$$\tilde D_au(\fxx)=\sup\{\lambda \in \RR\mid \fxx\in \tilde{\mathcal D}_a(\levelset_\lambda u)\};$$
$$\tilde E_au(\fxx)=\sup\{\lambda \in \RR \mid \fxx\in \tilde{\mathcal E}_a(\levelset_\lambda u)\}$$
and we call them respectively {\it affine function dilation} and {\it affine  function erosion}.

\begin{proposition} The affine function  dilation and erosion are translation invariant, contrast invariant and
standard monotone from $\mathcal F$  to $\mathcal F$. In addition they are affine invariant. Finally the  commutation
almost everywhere holds:
\begin{equation}\label{commutationthresholdaffine}
\levelset_\lambda(\tilde D_a u)=\tilde{\mathcal D}_a(\levelset_\lambda u) \hbox{ and } \levelset_\lambda(\tilde E_a
u)=\tilde{\mathcal E}_a(\levelset_\lambda u),
\end{equation}
almost everywhere for almost every $\lambda\in \RR$.
\end{proposition}

\begin{proof}  Since $\tilde{\mathcal D}_a$ and $\tilde{\mathcal E}_a$ are standard monotone and translation invariant,
this is a direct application of Theorem \ref{3.5bis}.  Since the set operators are not upper semicontinuous, there is
no chance to get a full commutation with thresholds. However, the commutation with thresholds almost everywhere holds
by Proposition \ref{commutationalmosteverywhere}.
\end{proof}
Let us finally point out that the affine function erosion and dilation are dual of each other.

\begin{proposition}\label{dualiteaffineerosiondilatationfonctions}
For $u\in  \mathcal F$, $\tilde E_au=-\tilde D_a(-u)$.
\end{proposition}

\begin{proof}
We wish to use the duality relations between $\tilde{\mathcal E}_a$ and $\tilde{\mathcal D}_a$ and the superposition
principle. This leads us to deal with upper level sets of $-u$ which are lower level sets of u. Thus we will need the
following relations,
\begin{equation} \label{lowerupperone}
\levelset_\lambda(-u)\subset \left(\levelset_{-\lambda +\varepsilon}u\right)^c \hbox{and}
\end{equation}
\begin{equation}\label{loweruppertwo}
\left(\levelset_{-\lambda+\varepsilon}(-u)\right)^c\subset \levelset_{\lambda-\varepsilon}u,
\end{equation}
for $\varepsilon>0$. We then  have

\begin{align*} \levelset_\lambda(-\tilde D_a(-u))
            &\stackrel{\eqref{lowerupperone}}{\subset} \left[\levelset_{-\lambda+\varepsilon}(\tilde D_a(-u))\right]^c
            \stackrel{\hbox{a.e.}}{=} \left[\tilde{\mathcal D}_a\levelset_{-\lambda+\varepsilon}(-u)\right]^c\\
           & \stackrel{\hbox{def.} \tilde{\mathcal E}_a}{=} \tilde{\mathcal
            E}_a\left(\levelset_{-\lambda+\varepsilon}(-u)\right)^c
            \stackrel{\eqref{loweruppertwo}}{\subset}\tilde{\mathcal E}_a(\levelset_{\lambda-\varepsilon}u)
\stackrel{\hbox{a.e.}}{=}  \levelset_{\lambda-\varepsilon}(\tilde E_au),
\end{align*}
where the a.e. relations are true for  every $\lambda$ and almost every $\varepsilon>0$ by the commutation with
thresholds almost everywhere \eqref{commutationthresholdaffine}. By  using the relation $\levelset_\lambda
v=\cap_{\varepsilon>0}\levelset_{\lambda-\varepsilon}v$ with $v=\tilde E_a u$, we obtain $\levelset_\lambda(-\tilde
D_a(-u))\subset \levelset_{\lambda}(\tilde E_au)$ almost everywhere for almost every $\lambda$. By taking
$\varepsilon<0$ it is easily checked that all inclusions in the above argument reverse. Thus almost all level sets of
$\tilde E_a u$ and  $-\tilde D_a(-u)$ are equal almost everywhere. By Corollary \ref{II.1.bis} and its consequence in
Exercise \ref{almosteverywhereequalityoflevelsets}   this implies
 that $\tilde E_a
u$ and $-\tilde D_a(-u)$ coincide almost everywhere. Since in addition these functions belong to $\mathcal  F$ and are
therefore continuous, they coincide everywhere.

\end{proof}
\begin{exercise} Prove the relations \eqref{lowerupperone} and \eqref{loweruppertwo} used in the proof of Proposition
\ref{dualiteaffineerosiondilatationfonctions}. \finex
\end{exercise}

\section{Principles for an algorithm}
This section won't give an explicit algorithm for performing affine erosions or dilations, but rather a general
principle from which algorithms can be derived. Since $\tilde{\mathcal D}_a$ is  obtained by duality from
$\tilde{\mathcal E}_a$ we'll focus on the implementation of affine erosion. Since as we shall see a curve will be split
into convex parts to apply the erosion, we can restrict ourselves to the case where $X$ is convex.

The intuitive idea is that $\tilde{\mathcal E}_aX$ could be obtained from $X$ by removing all chord-arc sets $C$
defined by $X$ and $\Delta$ that have area less than or equal to $a$, but this is not quite true.  A simple example is
given by taking for $X$ the open disk $D(0,1)$. Removing all chord-arc sets with area less than or equal to $a<\frac
\pi 2$ will leave a closed disk $D(0,r)$, whereas $\tilde{\mathcal E}_a D(0,1)$ is the open disk $D(0,r)$. We need only
make a small modification. If $C$ is a chord-arc set defined by $X$ and $\Delta$, we define $C^*$ by
$C^*=C\cup({\overline C}\cap\Delta)$.

\begin{proposition}\label{proposition12.8}Assume that $X$ is an open, convex and
bounded subset of $\RR^2$. Then $\tilde{\mathcal E}_aX$ can be obtained from $X$ by removing all of the modified chord
arc sets $C^*$ with area less than or equal to $a$.
\end{proposition}

\begin{figure}[!t]
\setkeys{Gin}{width=5cm} \centerline{
\includegraphics{fig12.03.1.eps}
} \caption[Illustration of   Corollary
\ref{erosionaffinefacile}]{\label{erosionaffinefacilefigure}
Illustration for Proposition \ref{proposition12.8}.}
\end{figure}

\begin{proof}Let $C$ be any chord-arc set defined by $X$ and a
line $\Delta$ such that ${\rm area}(C)\leq a$. Then we claim that
$\fxx\in C^*$ implies that $\delta(\fxx, X^c)\leq a^{1/2}$. To see
this, let $\Delta'$ be the line parallel to $\Delta$ that contains
$\fxx$. The lines $\Delta$ and $\Delta'$ each define two open
half-planes, which we denote by $R$ and $L$ and $R'$ and $L'$.
Without loss of generality, we may assume that $\Delta'\subset R$,
or equivalently, that $\Delta\subset L'$. (See Figure
\ref{erosionaffinefacilefigure}.)

Consider the sets $CA_i(\fxx,\Delta',X^c)$, $i=1,2$. These are the
connected components of
$\RR^2\setminus({\overline{X^c}}\cup\Delta')=({\overline{X^c}})^c\cap(\Delta')^c=X^\circ\setminus\Delta'$
that contain $\fxx$ in their boundaries. One of these sets, say,
$CA_1(\fxx,\Delta',X^c)$ is in $R\cap R'$. Now
${\overline{CA_1(\fxx,\Delta',X^c)}}\cap C\not=\emptyset$, since
both sets contain $\fxx$. This means that
${CA_1}(\fxx,\Delta',X^c)\cup C$ is connected, and since $C$ was a
maximal connected set in $X\setminus\Delta$ we conclude that
$CA_1(\fxx,\Delta',X^c)\subset C$. Thus the area of
$CA_1(\fxx,\Delta',X^c)$ is less than or equal to $a$, so
$\delta(\fxx,X^c)\leq a^{1/2}$, and $\fxx\not\in\tilde{\mathcal
E}_aX$.

For the converse, we must show that if a point was eroded, then it
had to have been in a set $C^*$, where $C$ is a chord-arc set with
area less than or equal to $a$. Our proof uses a result that we
prove in the next exercise \ref{exercise12.4}, namely, that if
$\delta(x,X^c)\leq a^{1/2}$, then there is a line $\Delta$ that
contains $\fxx$ such that $\delta(x,X^c)=[{\rm area}(C)]^{1/2}$,
where $C$ is a chord-arc set defined by $X$ and $\Delta$. Then for
this $C$, $\fxx\in C^*$ and ${\rm area}(C)\leq a$.
\end{proof}

\section{Affine Plane Curve Evolution Scheme. \label{sectionlionel}}

Curve evolution applied to image level lines also yields an image evolution.  Osher and Sethian proposed in order to
simulate the evolution of a surface by the curvature motion by evolving its distance function by a finite difference
scheme of the curvature motion. This strategy is quite well justified in dimension 3 but less in dimension 2 where
level lines are simple Jordan curves. One can instead extract all level lines of the image and compute their evolution
by the affine shortening. Each curve will be numerically represented as a polygon. The affine shortening is numerically
defined as an {\it alternate filter}, which alternates affine erosion and  affine dilation with a small parameter $a$.


\subsection{A fast algorithm\label{sec:fastalgorithm}}

The affine erosion of a set $X$ is not simple to compute, because it is a  strongly non local process. However, if $X$
is convex, it has been shown in \cite{Moisan:1998:APC} that it can be exactly computed in linear time. In practice, $c$
will be a polygon and the exact affine erosion of $X$
---whose boundary is made of straight segments and pieces of hyperbolae---
is not really needed~; numerically, a good approximation by a new polygon is enough. Now the point is that we can
approximate the  alternate affine erosion and dilation of $X$ by computing the affine erosion of each {\em convex or
concave component} of $c$, provided that the erosion/dilation area is small enough.

\bigskip

The algorithm consists in the iteration of a four-steps process~:

\begin{enumerate}
\item {\bf Break the curve into convex or concave parts.}
This operation permits to apply the affine erosion to convex pieces of curves, which is much faster (the complexity is
linear) and can be done simply in a discrete way. The main numerical issue is to take into account the finite precision
of the computer in order to avoid spurious (small and almost straight) convex components.
\item {\bf Sample each component.}
At this stage, points are removed or added in order to guarantee an optimal representation of the curve that is
preserved by step 3.
\item {\bf Apply discrete an affine erosion to each component.}
\item {\bf Concatenate the pieces of curves obtained at step 3.}
This way, we obtain a new closed curve on which the whole process can be applied again.
\end{enumerate}

\bigskip


The curve has to be broken at points where the sign of the determinant
$$d_i = \D{P_{i-1}P_i,P_iP_{i+1}}$$
changes. Numerically, we use the formula
\begin{equation}
d_i = (x_i-x_{i-1})(y_{i+1}-y_i) - (y_i-y_{i-1})(x_{i+1}-x_i) \label{di.num}
\end{equation}
Since we are interested in the sign of $d_i$, we must be careful because the finite numerical precision of the computer
can make this sign wrong. Let us introduce the relative precision of the computer
\begin{equation}
\varepsilon_0 = \max\{x>0, \; (1.0\oplus x)\ominus 1.0 = 0.0 \}. \label{defprec.equ}
\end{equation}
In this definition, $\oplus$ (resp. $\ominus$) represent the computer addition (resp.  substraction), which is not
associative. When computing $d_i$ using (\ref{di.num}), the computer gives a result $\tilde{d}_i$ such that
$|d_i-\tilde{d}_i| \leq e_i$, with \begin{eqnarray*} e_i = \varepsilon_0 \left( \bigh \right. & \; &
|x_i-x_{i-1}|(|y_{i+1}|+|y_i|)
+ (|x_i|+|x_{i-1}|)|y_{i+1}-y_i| \\
&+& \left. |y_i-y_{i-1}|(|x_{i+1}|+|x_i|) + (|y_i|+|y_{i-1}|)|x_{i+1}-x_i| \;\;\;\bigh\right).
\end{eqnarray*}
In practice, we take $\varepsilon_0$ a little bit larger than its theoretical value to overcome other possible errors
(in particular, errors in the computation of $e_i$). For four-bytes C {\it float} numbers, we use $\varepsilon_0 =
10^{-7}$, whereas the theoretical value (that can be checked experimentally using (\ref{defprec.equ})) is
$\varepsilon_0 = 2^{-24} \simeq 5.96 \;10^{-8}$. For eight-bytes C {\it double} numbers, the correct value would be
$\varepsilon_0 = 2^{-53} \simeq 1.11 \;10^{-16}$

\bigskip

The algorithm that breaks the polygonal curve into convex components consists in the iteration of the following
decision rule~:

\begin{enumerate}
\item If $|\tilde{d}_i| \leq e_i$,
then remove $P_i$ (which means that to new polygon to be considered from this point is
$P_0P_1...P_{i-1}P_{i+1}...P_{n-1}$)
\item If $|\tilde{d}_{i+1}| \leq e_{i+1}$,
then remove $P_{i+1}$
\item If $\tilde{d}_i$ and $\tilde{d}_{i+1}$ have opposite signs,
then the middle of $P_i, P_{i+1}$ is an inflexion point where the curve must be broken
\item If $\tilde{d}_i$ and $\tilde{d}_{i+1}$ have the same sign,
then increment $i$
\end{enumerate}

This operation is performed until the whole curve has been visited. The result is a chained (looping) list of convex
pieces of curves.


\bigskip

\noindent\noindent $\bullet$ {\bf Sampling}

At this stage, we add or remove points from each polygonal curve in order to ensure that the Euclidean distance between
two successive points lies between $\varepsilon$ and $2\varepsilon$ ($\varepsilon$ being the absolute space precision
parameter of the algorithm).


\bigskip

\noindent\noindent $\bullet$ {\bf Discrete affine erosion}

This is the main step of the algorithm~: compute quickly an approximation of the affine erosion of scale $\sigma$ of
the whole curve.

\bigskip

The first step is the computation of the ``area'' $A_j$ of each convex component ${\cal C}^j = P^j_0P^j_1...P^j_{n-1}$,
given by
$$A_j = \frac 1 2 \sum_{i=1}^{n-2}\D{P^j_0P^j_i,P^j_0P^j_{i+1}}.$$
Then, the effective area used to compute the affine erosion is
$$\sigma_e = \max\left\{\frac{\sigma}{8},\min_j A_j\right\}.$$
We restrict the erosion area to $\sigma_e$ (which is less than $\sigma$ in general) because the simplified algorithm
for affine erosion (based on the breaking of the initial curve into convex components) may give a bad estimation of the
continuous affine erosion+dilation when the area of one component is less than the erosion parameter. The term
$\sigma/8$ is rather arbitrary and guarantees an upper bound to the number of iterations required to achieve the final
scale.

\bigskip

Once $\sigma_e$ is computed, the discrete erosion of each component is defined as the sequence of  middle points of all
segments $[AB]$ such that
\begin{enumerate}
\item $A$ and $B$ lie on the polygonal curve
\item $A$ or $B$ is a vertex of the polygonal curve
\item the area enclosed by $[AB]$ and the polygonal curve is equal
to $\sigma_e$
\end{enumerate}
These points are easily computed by keeping in memory and updating the points $A$ and $B$ of the curve plus the
associated chord area.

\bigskip

Notice that if the convex component is not closed (which is the case if the initial curve is not convex), its endpoints
are kept.


\begin{figure}[th]
\setkeys{Gin}{width=3.5cm}
 \centerline{
\includegraphics{DDIR/lionel1bis.eps}
\includegraphics{DDIR/lionel3bis.eps}
\includegraphics{DDIR/lionel6bis.eps}
} \caption{ Affine scale space of a ``hand'' curve, performed with the alternate affine erosion-dilation scheme.
(scales 1, 20, 400). Experiment : Lionel Moisan.}\label{HandMoisan}
\end{figure}



\noindent\noindent $\bullet$ {\bf Iteration of the process}



To iterate the process, we use the fact that if $E_{\sigma}$ denotes the affine erosion plus dilation operator of area
$\sigma$, and $h=(h_i)$ is a subdivision of the interval $[0,H]$ with $H= T/\omega$ and $\omega =
\frac{1}{2}\left(\frac{3}{2}\right)^{2/3}$, then as we are going to show further,
$$E_{(h_1-h_0)^{3/2}}\circ E_{(h_2-h_1)^{3/2}} \circ ...
\circ E_{(h_n-h_{n-1})^{3/2}} \;\;\left(\bigh c_0 \right) \;\; \longrightarrow \;c_T$$ as $|h| = \max_i h_{i+1}-h_i
\rightarrow 0$, where $c_T$ is the affine shortening of $c_0$ up to scale $T$, described  by the evolution equation
\eqref{eq615x}.  We refer to Chapters \ref{chap:AsymptoticAffineInvariant} and \ref{CurvatureequationsandIterated} for
a proof of the equivalence between this affine invariant curve evolution and the above iterated alternate affine
erosion-dilation scheme.

\bigskip

\noindent\noindent $\bullet$ {\bf Comments}

The algorithm takes a curve (closed or not) as input, and produces an output curve representing the affine shortening
of the input curve (it can be empty if the curve has disappeared) . The parameters are
\begin{itemize}
\item $T$, the scale to which the input curve must be smoothed
\item $\varepsilon_r$, the relative spacial
precision at which the curve must be numerically represented (between $10^{-5}$ and $10^{-2}$ when using four bytes C
{\it float} numbers).
\item $n$, the minimum number of iterations required to compute the
affine shortening (it seems that $n \simeq  5$ is a good choice). From $n$, the erosion area $\sigma$ used in step 3 is
computed with the formula
$$\sigma^{2/3} = \frac{\alpha \cdot T^{4/3}}{n}.$$
Notice that thanks to the $\sigma/8$ lower bound for $\sigma_e$, the effective number of iterations cannot exceed $4n$.
\item $R$, the radius of a disk containing the input curve, used to obtain
homogeneous results when processing simultaneously several curves. The absolute precision $\varepsilon$ used at step 2
is defined by $\varepsilon = R \varepsilon_r$.
\end{itemize}


The algorithm has linear complexity in time and memory, and its stability is ensured by the fact that each new curve is
obtained as the set of the middle points of some particular chords of the initial curve, defined themselves by an
integration process (an area computation). Hence, no derivation or curvature computation appears in the algorithm.



\section{Exercises}


\begin{exercise}The aim of this exercise is to prove that a
one-to-one mapping $\tilde A:\RR^2\to\RR^2$ that preserves parallelism must be of the form $\tilde A(\fxx)=A\fxx+\fxb$,
where $A$ is a linear mapping and $\fxb$ is a fixed vector. The preservation of parallelism is defined as follows: If
any four points $\fxx_1$, $\fxx_2$, $\fxx_3$, and $\fxx_4$ satisfy $\fxx_1-\fxx_2=\lambda(\fxx_3-\fxx_4)$ for some
$\lambda\in\RR$, then there exists a $\mu\in\RR$ such that ${\tilde A}\fxx_1-{\tilde A}\fxx_2=\mu({\tilde
A}\fxx_3-{\tilde A}\fxx_4)$.
\begin{enumerate}[(i)]\setlength\itemsep{2pt}
\item Let ${\bm i}$ and ${\bm j}$ be the usual orthonormal basis for $\RR^2$ and write $\fxx=x{\bm i}+y{\bm j}$. Define $A$ by $A\fxx={\tilde A}\fxx-{\tilde A}0$. Show that there are two real function $\mu_i:\RR\to\RR$, $i=1,2$, such that $A(x{\bm i})=\mu_1(x)A{\bm i}$ and $A(y{\bm j})=\mu_2(y)A{\bm j}$.
\item Notice that $A$ preserves parallelism and that $A0=0$.
\item Show that $A\fxx=\mu_1(x)A{\bm i}+\mu_2(y)A{\bm j}$.
\item Show that $\mu_1(\lambda)=\mu_2(\lambda)$.
\item We wish to show that $\mu_1(x)=x$. One way to do this is to prove that $\mu_1:\RR\to\RR$ is an isomorphism. This can be done using the fact that $\fxx_1-\fxx_2=\lambda(\fxx_3-\fxx_4)$ implies that $A\fxx_1-{A}\fxx_2=\mu({ A}\fxx_3-{A}\fxx_4)$. Once you have shown that $\mu_1:\RR\to\RR$ is an isomorphism, you can quote the result that says any isomorphism of $\RR$ onto itself must be $x\mapsto x$, or you can prove this result. \finex
\end{enumerate}
\end{exercise}


\begin{exercise} A justification of the main step of Moisan's algorithm. We refer to the "discrete affine erosion" step
of the Moisan algorithm described in Section  \ref{sec:fastalgorithm}. It is said that  a polygon approximating a the
affine erosion of a convex set can be obtained by finding many chord-arc sets and  taking the middle points of their
chords as vertices of the eroded polygon. This follows from the fact that the chords of two nearby chord-arc sets with
same area tend to  meet at their common middle point.

\begin{enumerate} \item Let $abcd$ be a quadrilateral with diagonals $ac$ and $bd$. Let $i$ be the crossing point of
$ac$ and $bd$. Assume that the areas of the triangles $abi$ and $icd$ are equal and that $a$ and $c$  are fixed points
while $b$  and $d$ move in such a way that $d\to c$ and $b\to a$.  Prove that the lengths $|ia|, |ib|, |ic|, |id|$ all
tend to $\frac{|ac|}2.$  Hint: to do so, prove that the area of the triangle $idc$ is equivalent to
$\frac{\theta.|id|^2}2$, where $\theta$ is the angle of $id$ with $ic$.

\item Let $C$ be a convex Jordan curve surrounding a convex set $X$ and let $\Delta$ be a straight line meeting $C$ at
$a$ and $c$. Call $CA$ one of the two chord-arc sets defined by $\Delta$ and $C$. Let $b$ be a point close to $a$ on
$C$ and $d$ a point close to $c$ chosen in such a way that the chord-arc $CA'$ defined by the line $\Delta'=bd$ and $C$
has the same area as $CA$.  Apply the result of the first question with $b\to a$.

\item Deduce from this and Proposition \ref{proposition12.8} that the Moisan algorithm computes an approximation to an
affine erosion of a polygon.

\end{enumerate}
\finex
\end{exercise}
\begin{exercise}\label{exercise12.4} Assume that $X$ is convex, open and
bounded. We refer to Figure \ref{figdef} below for the definitions of the various objects. Thus, $\Delta(0)$ is an
arbitrary line that contains $\fxx$ and $C(0)$ is the connected component of $X\setminus\Delta(0)$ on the arrow-side of
$\Delta(0)$ whose boundary contains $\fxx$. $C(\varphi)$ is the connected component of $X\setminus\Delta(\varphi)$ on
the arrow-side of $\Delta(\varphi)$ whose boundary contains $\fxx$. Since $X$ is open, there is an $r>0$ such that the
disk $D(x,r)$ is contained in $X$; since $X$ is assumed to be bounded, there is an $R>0$ such that $X\subset D(x,R)$.
\begin{figure}[!h]
\setkeys{Gin}{width=10cm}
\centerline{
\includegraphics{fig12.04.1.eps}
}
\caption[Definition of $C(0,\varphi)$]{\label{figdef}Definition of
$C(0,\varphi)$. The set $C(0,\varphi)$ is the connected component
of $X\setminus (\Delta(0)\cup\Delta(\varphi))$ that lies in the
direction of the arrows.
}
\end{figure}
\begin{enumerate}[(i)]\setlength\itemsep{2pt}
\item Show that $C(0,\varphi)\subset C(0)$ and $C(0,\varphi)\subset C(\varphi)$.
\item Show that ${\rm area}(C(0)\cap C(0,\varphi)^c)\to0$ as $\varphi\to0$ and similarly
 that ${\rm area}(C(\varphi)\cap C(0,\varphi)^c)\to0$ as $\varphi\to0$.
\item Deduce that ${\rm area}(C(\varphi))\to{\rm area}(C(0))$ as $\varphi\to0$.
\end{enumerate}
This shows that ${\rm area}(C(\varphi))$ is a continuous function
of $\varphi$. Thus, the $\inf_{\Delta(\varphi)}{\rm
area}(C(\varphi))$ is attained, which means that for every
$\fxx\in X$ there is some $\varphi$ such that
$\delta(\fxx,X^c)=[{\rm area}(C(\varphi))]^{1/2}$.

Is the above result still true if $X$ is not convex?
 \finex
\end{exercise}



\section{Comments and references}

Shape-recognition algorithms in the plane are clearly more robust
if they are affine invariant, if only because most optical devices
that copy plane images (photocopiers) or that convert plane images
to digital information (scanners, faxes) create a slight affine
distortion. Also, all diffeomorphisms are locally affine.
Affine-invariant techniques for matching shapes are described in
\cite{Hummel:1988:AIM}; discussions of the role of affine and
projective invariance for object recognition can be found in
\cite{Bose:1996:MBO}, \cite{Weiss:1995:LPA}, and
\cite{Kempenaers:1991:SRU}. Corners and T-junctions can appear in
images with arbitrary angles, and the detection of angles between
straight lines should be affine invariant. Algorithms for
affine-detection of angles are proposed in \cite{Blom:1992:AIC},
\cite{Alvarez:1997:AMM}, \cite{Vasselle:1994:FCC}, and
\cite{Deriche:1993:CAC}. See Merriman, Bence, and Osher
\cite{Merriman:1994:MMJ} for a very original numerical view for
filtering multiple junctions. Because of the relevance to computer
vision, there has been considerable research devoted to looking
for affine-invariant definitions of classical concepts in
geometric measure theory and integral geometry. An interesting
attempt to define an ``affine-invariant length'' and an
``affine-invariant dimension'' analogous to Hausdorff lengths and
dimensions is given in  \cite{Dibos:1996:ALA}. The diameters of
the sets of a Hausdorff covering are simply replaced by their
areas. Several attempts to define affine-invariant analyses of
discrete sets of points are described in \cite{Geraets:1995:ASS}
and \cite{Sapiro:1997:SSC}. An affine-invariant symmetry set
(skeleton) for shapes is defined in \cite{Giblin:1997:AIS}; the
1/3 power law of planar motion perception and generation is
related to affine invariance in \cite{Pollick:1997:CAV}. Some of
the techniques on affine erosions and dilations presented in this
chapter were announced in \cite{Lisani:2000:AIM}. We have made
liberal use of the Matheron formalism for monotone set operators
\cite{Matheron:1975:RSI}.


The fully invariant affine curve evolution geometric algorithm which we presented  was found by Moisan
\cite{Moisan:1998:APC}. Its implementation for {\it all} level lines of an image was realized in Koepfler
\cite{Koepfler:1999:GMR}. Cao and Moisan \cite{CaoMoisan:2000:CDE} have generalized this curve evolution approach to
curvature motions  at arbitrary speed of the curvature. They succeeded in numerically moving curves at velocities
proportional to the power 10 of curvature. Lisani et al. \cite{Lisani:2000:AIM} and later Cao, Gousseau, Sur and
Mus\'{e} \cite{?????} have used the affine curve evolution scheme for  shape recognition and image comparison
algorithms.
