This chapter corresponds to a paper written in collaboration with J.M. Morel and S. Solimini~\cite{KoeMS}. It is devoted to numerical analysis of the simplest among the models discussed above : the Mumford and Shah piecewise constant model.

\section[Introduction]{Introduction.}

Let us recall the principles which we discussed in chapter 1 and which we shall adopt in this chapter.

\subsection[Principes g\'en\'eraux des m\'ethodes de segmentation]{General principles of segmentation devices.}

\begin{enumerate}
\item The first principle which we shall adopt is that the boundary detection problem must follow some universal rules. In other terms, we admit the possibility of a universal boundary detection device, definable and analysable  independently from the kind of channels (grey level, colour, texture, \ldots) to be used as input for the segmentation (\cite{BecSI,MaliP2,Ju3}).  This first principle allows us to try to get a good mathematical understanding of the segmentation problem, by considering only the grey level segmentation.  It is the simplest case of boundary detection, and it eliminates every early discussion about the concept of texture.  (By ``boundary in an image'', we mean the boundary in the topological sense : it is the boundary  of an homogeneous region of the image.  Thus boundaries are different from edges obtained by some local filtering.)

\item A second principle which we adopt in the following is  that an algorithm for boundary detection must be  scale and space invariant.  By space invariance, we mean that all points of the analysed picture will be treated on the same way, and therefore a segmentation device must be translation and rotation invariant.  Since boundaries may be present at every scale, the scale invariance only means that we shall consider multiscale segmentation algorithms, depending on a scale parameter $\lambda$ which we do not try to estimate and leave to the user's choice.

\item Finally we shall adopt a principle without which no discussion about segmentation can even start, and which we call comparison principle.  It states that given two different segmentations of a datum, we shall always be able to decide which of them is considered as better than (or equivalent to) the other. Thus we assume the existence of some  total ordering over all possible segmentations, and this can be simply achieved if this ordering is reflected by some real functional E such that if $E(K_1)<E(K_2)$, then the segmentation $K_1$ has to be considered ``better'' than the segmentation $K_2$.  For instance, this principle is verified by segmentation devices based on some Gibbs energy functional like in~\cite{GemG}.  It is not verified by the region growing methods based on thresholds \cite{Pav1,Pav2,PavL,Zu1}, nor by the edge detection devices~\cite{Marr3,MaliP1}. 
\end{enumerate}

\subsection[Formalisation]{Formalization.}
We define an image $g$ as a scalar function, defined on the image domain $\Omega$ (generally a rectangle).  The function $g$ may also be vectorial, in the case where it has several channels for characterizing textures, histograms,  colors, \ldots   That does not change anything in the theorems and proofs that we later state.   The only hypothesis is that these channels have been defined in order to be good indicators of the similarity -- or difference -- of points of the picture, and therefore good indicators for the autosimilarity of regions.We seek for a segmentation, that is, a partition of this rectangle into a finite set of regions, each of which corresponds to a part of the image where $g$ is as constant as possible.  Moreover, we wish to compute explicitly the region boundaries and of course control their regularity and location.  Since by the comparison principle, all of these criteria must be taken into account in the functional $E$, we see that this functional necessarily contains terms which control :	
\begin{description}
\item[-] the autosimilarity of each region with respect to the chosen 	channels.  Those channels must be as constant as possible on 	each region.
\item[-]  the size, location and regularity of the boundaries.
\end{description}
Denote by $K$ the whole boundary set of the segmentation.  According to these principles, a natural energy functional for segmentation will contain two terms, a two dimensional term for the autosimilarity of the zones which will roughly speaking measure the variance of g on each connected component of $\Omega\setminus K$ and a one dimensional one for controlling the length, and eventually the adequacy of location of the boundaries.  Such a generic justification is developped e.g. in~\cite{MumS1,MumS2,MumS3}. By the space invariance principle, those terms will be integrals terms, the two dimensional  one being an integral with respect to the Lebesgue measure and the one dimensional an integral with respect  to the Hausdorff measure or ``length'' along the boundaries.   Clearly, the weights given to the terms of the functional will be left to our choice. Consider for example the energy used by Mumford and Shah :
$$E(u, K) = \int_{\Omega\setminus K}|\nabla u|^2 d\!x  + \int_\Omega (u-g)^2d\!x  + \int_K d\!\sigma\;,$$
Both first integrals are bidimensional and the third one is with respect to the uniform measure $d\!\sigma$ supported by $K$.  This energy means that in a ``good'' segmentation $(u, K)$, the curves of $K$ should be the boundaries of homogeneous areas in the image and $u$ a sort of mean or, more generally, a regularized version of $g$ in the interior of such areas. The third term gives a control on the length, and therefore on the regularity of the boundaries of $K$ ( see below ).  This kind of functional represents of course a compromise between accuracy of the regions and parcimony of the boundaries: in case of grey level segmentation, as noticed in Zucker~\cite{Zu1} or Haralick and Shapiro~\cite{HarS}, a pure region growing would simply put together the pixels with similar grey levels. But this generates very nonsmooth boundaries and therefore also ``small'' or ``thin'' regions. \\
 So if no control is made on the boundaries, one needs additional criteria and thresholding to achieve a decent segmentation.   A functional like the above functional is designed to avoid this kind of mixed methods : one hopes having all the criteria put together in the same functional.   For instance, the functional used for the so called ``snakes''~\cite{KasWT,AmiTW} uses a more sophisticated third term for controlling both location (the snake is forced to be close to edges)  and smoothness of the boundary.  Many early functionals in image analysis had only two dimensional energy terms (which were coupled with some thresholding criteria~\cite{Pav1,Zu1}).  Note that the functional proposed in Blake and Zisserman~\cite{BlakZ} has no term  imposing directly that the boundary is close to pixels having a high gradient.   


\subsection[Choix des propri\'et\'es et algorithmes pour la segmentation]{Choice of properties and algorithms for segmentation.}

The algorithmic description given by  Pavlidis and Liow~\cite{PavL} (see page~\pageref{ref_PavL}) is an excellent illustration of the level of sophistication to which the segmentation methods have arrived, by superposing several tricky -- but probably also necessary -- devices arisen in the two last decades. Now, the question which is naturally raised by the coexistence of energy functionals on one side,  and of segmentation devices on the other is wether they match in any aspect, and how.

Our purpose is to classify the properties which are sought by those devices and to decide which of them are basic, and which can be deduced.   Beyond being a way to attain certainty, mathematical proofs are a powerful tool for obtaining such a classification of properties.  Once this hierarchy among tools has been established, one may hope to simplify the algorithms and to make them completely transmissible and reproducible.  Our aim in this chapter is to apply this method and to classify terms like ``small or thin region elimination'', ``splitting'', ``merging'', ``snakes'', ``energy minimizing'', ``region growing'', which have proved to be so necessary in most discussions about segmentation, all this following the ideas developed in chapter~\ref{chSeg}. We will give here with more detail the simplest model of Mumford and Shah~\cite{MumS2}. Recall that according to this model the segmentation $(u,K)$ should be obtained by minimizing the functional
\begin{equation}
\label{MS_cpm}
E(u, K) =  \int_{\Omega\setminus K}(u-g)^2d\!xd\!y + \lambda \ell(K), 
\end{equation}
where $K$ is  a union of boundaries in $\Omega$ with Hausdorff length $\ell(K)$, and $u$ is piecewise constant on $\Omega\setminus K$.   The constant $\lambda$ represents the scale parameter of the functional and measures the amount of boundary : if $\lambda$ is low, a lot of boundaries are allowed and we shall get a fine segmentation.  As  $\lambda$ increases, the segmentation gets coarser and coarser.  Similar functionals have been  recently introduced by several authors in order to modelize physical phenomena like phase transition~\cite{FoT} and liquid crystals ~\cite{DeG,AmbDeG,CarDeGL} .
\medskip

In what follows, we shall focus on functional \Pref{MS_cpm} because it is the simplest one containing most of the algorithmic difficulties of such functionals.  Moreover, it is the only one for which a complete mathematical analysis is available.  Indeed, Mumford and Shah have proved in~\cite{MumS2} that the boundary set obtained by this functional has the following geometric property : either the points of K are regular (at least $C^1$) or the singular points are of two types, namely, triple points where three branches meet with $120^\circ$ angles and boundary points where $K$ meets the boundary of $\Omega$ at a $90^\circ$ angle. Moreover, the boundaries of the segmentation verify variational inequalities of the kind 
\begin{equation}
\label{MS_curv}
(u^+-g^-)^2 - (u^--g^-)^2 \leq {\rm curv}(x) \leq (u^--g^+)^2 - (u^+-g^+)^2,
\end{equation}
 where $u^+$ and $u^-$ denote the values of $u(x)$ on both sides of the boundary.

In~\cite{MorS1,MorS3} Morel and Solimini have given an elementary and constructive proof of the above theorem.\\
Of course, the fact that the crossing points must be ternary proves that such a functional gives no hope of accurate segmentations.  But this is, in our view, secondary, because one can improve the functional by adding or modifying boundary terms (of the kind used for snakes) or surface terms (for instance by imposing that $u$ is a linear, quadratic or cubic spline, \ldots ).  This would not change the nature of the proofs and methods which we discuss here and which apply to most energy functionals mentioned above.  Note however, that the general functional of Mumford and Shah has a different structure.  As proved in~\cite{BlatM2,CarLPP,MumS2}, it allows open boundaries and therefore the merging methods which will be discussed here are not adequate.  Moreover, the proof of the ``Mumford and Shah conjecture'', which states that this functional would lead to a finite set of smooth boundaries is not achieved.  The best available result~\cite{DalMMS1,DalMMS2} is that the minimizing boundaries (which in some weak sense exist~\cite{Amb}) can be approximated by a finite number of curves.  No regularity result is available, and we see it difficult to comment now mathematically the first and interesting numerical simulations~\cite{BlakZ} of this problem. An attempt to do so is however presented in chapter \ref{chRect}. Let us therefore return to our ``simplest functional'' \Pref{MS_cpm}.  It is well known that functionals  of this kind may have many local minimizers. In the case of the functional \Pref{MS_cpm}, it is easy to give explicit examples.  Moreover, a reasonable conjecture is that to find a minimizer, or even to prove a posteriori  that some computed local minimum is global leads to a NP-complete problem.
\medskip

One has thus to choose between two strategies :
\begin{itemize}
\item The global minimization by simulated annealing methods, which leads to huge computations, but ensures that in some asymptotic sense, the global minimum is attained~\cite{GemG}.
\item Another way is then to define some concept of local minimum which should be more accessible to fast computations and verify the same properties which were seeked for the global minimum.
\end{itemize}
For instance, in the case of simulated annealing, a recent tendency is to define some faster, parallel processes, but which do not pretend to find a global minimum anymore~\cite{Az1,Az2}.  The homotopy method of Blake and Zisserman~\cite{BlakZ} also seeks for ``good'' local minima.  (It seems to be close to a $\Gamma$-convergence device suggested by the mathematical school of De Giorgi~\cite{AmbT} and developed by Tom Richardson in his Phd. Dissertation at MIT~\cite{Ric}).One needs a theory to do that in the deterministic approach to which the segmentation devices mentioned above belong.  In the next section we shall give some basic definitions and notations concerning our ``simplest'' energy functional.  In sections~\ref{reg_ssec_T} and \ref{reg_ssec_P}, we give a precise account of topological properties and the proofs of the announced results concerning segmentations obtained by ``merging''. The definition and properties of what we could call the ``simplest possible'' recursive merging algorithm which will be described in chapter~\ref{chIm-Exp}, there will also be shown results obtained by running this algorithm.


\section[D\'efinitions et notations]{Definitions and notations.}
\bigskip

\begin{itemize}
\item The function $g$. It is a bounded measurable real function on a rectangle $\Omega$ (more generally for $g : \Omega\mapsto\R^N$, $N\geq2$ the same result holds). Without loss of generality we assume  that $|g(x,y)|\leq 1$. 
\item The {\em energy $E(K)$} : note that given  the boundaries $K$, the corresponding minimal $u$ is completely defined by the fact that its value on each connected component of $\Omega\setminus K$ is equal to the mean value of $u$ on this connected component.  Thus we shall always assume in the following that to each $K$ is associated this unique $u$.  Therefore we shall write $E(K)$ instead of $E(u, K)$.
\item {\em Regions}, or connected components of $\Omega\setminus K$: we shall denote them by $(O_i)_i$.
\item {\em Common boundary} of two areas $O_i$ and $O_j$ :  we denote it by $\partial(O_i, O_j)$.  It is contained in $K$.  If $i=j$, $\partial O_i$ denotes the boundary of $O_i$.
\item {\em Two dimensional measure} of $O_i$ : denoted by $|O_i|$.
\item {\em Isoperimetric inequality} in $\R^2$ and $\Omega$ : denote by $O$ a region in $\R^2$.  Then one has
$$\ell(\partial O) \geq 2\sqrt{\pi}\cdot \sqrt{|O|}\;.$$
In the case of $\Omega$, the same kind of inequality holds for the {\em relative boundary} of $O$ in $\Omega$, $\partial O\cap\Omega$, with a smaller constant $C$ : 
$$\ell(\partial O\cap\Omega)\geq C\cdot\sqrt{|O|}\;.$$
Since there is no ambiguity, $\Omega$ being fixed, we still denote by $\partial O$ the relative boundary of $O$ in $\Omega$.  By $\ell(\partial O)$ we mean the length of the boundary of $O$.  For a general definition of the length of the boundary (``perimeter'') of a region in the plane, see~\cite[\S 4.5.1]{Fed} or~\cite[\S 14]{Si-L}. 
\end{itemize}

\begin{DefinitionE} A segmentation $K$ will be called normal if every subsegmentation $K'$ of $K$ verifies $E(K') > E(K)$. 
\end{DefinitionE}

By a subsegmentation of $K$, we mean a segmentation obtained by merging an arbitrary number of adjacent regions. The normality of a segmentation means that no merging operation of a set of regions of the segmentation $K$ can decrease the energy.  This definition implies in particular that if $K$ is normal, no boundary between two regions of the segmentation may be removed without increasing the energy $E$.  

\begin{DefinitionE} A segmentation $K$ will be called 2-normal if  for every pair of regions $O_i$ and $O_j$, the new segmentation $K'$ obtained by merging these regions verifies  $E(K') > E(K)$. 
\end{DefinitionE}

We shall consider only segmentations having the following properties, which are easy to check for computationally defined segmentations.
\begin{description}
\item[a)]  The number of regions is finite.   In other terms, $\Omega\setminus K$ has a finite number of connected components.
\item[b)] No region has internal boundaries. In other terms, the interior of the closure of each region $O$ is equal to the interior of $O$.  Indeed, if this is not the case, one can remove the internal  boundaries without increasing the energy. This property is called the ``1-normality'' (compare to the definitions above).
\item[c)] The segmentations are made of piecewise affine curves.
\end{description}
Let us introduce the framework in which we will study the toplogical properties of affine 1-normal segmentations.
\begin{itemize}
\item A {\em curve} $c$ from $[0,1]$ into $\Omega$ has {\em tips} $c(0)$ and $c(1)$, all other points of the range of $c$ are {\em interior points}.
\item {\em Geometrical support} of a curve $c$ : denoted by $S(c)$, it is the range of the curve $c$. For several curves it is the union of the ranges.\\
For instance $K=\Disp{\bigcup_i S\left(c_i\right)}$.
\item A segmentation is said to be {\em piecewise affine} -- resp. {\em $C^1$} -- if the corresponding $c_i$ are {\em piecewise affine} -- resp. {\em $C^1$} --. A {\em polygon} is a connected region of an affine segmentation.
\item {\em Geometrical crossings} : all the points of $K$ where either a curve meets the interior of another, either three curves at least have a common tip, or a curve meets $\partial\Omega$.
\item {\em Geometrical curve} : subset of $K$ which is in the geometrical support of a curve $c$ such that its boundary is contained in the set of geometrical crossings and that no one of its interior points is a geometrical crossing.
\item A {\em Jordan curve} is a continuous curve, such that for all $\sigma ,\sigma'\in]0,1[\,:\, c(\sigma)\neq c(\sigma')$ if $\sigma\neq\sigma'$; if $c(0)=c(1)$ the Jordan curve is said to be {\em closed}.
\end{itemize}

\section[Propri\'et\'es des segmentations affines 1-normales]{Topological properties of affine 1-normal segmentations.}
\label{reg_ssec_T}
\bigskip

Let us recall a classical result on Jordan curves (for a proof see for example \cite{Ale})
\begin{Lemma} \label{reg_L1}
Every closed Jordan curve $c$ divides the plane in exactly two connected components, one is bounded ``enclosed by $c$'' and one unbounded.
\end{Lemma}
We will say that a closed Jordan curve $c$ {\em encloses} a part of the plane if this part is included in the bounded connected component delimited by $c$.

\medskip

\begin{Lemma}\label{reg_L2}
Let $c_0$, $c_1$, \ldots , $c_p$, \ldots, be closed Jordan curves such that for every $p$ : $S(c_p)\setminus \Disp{\bigcup_{k<p}}S(c_k)\neq\emptyset$. Then for every $p$ , $\R^2\setminus\Disp{\bigcup_{k<p}}S(c_k)$ has at least $p+1$ connected components.
\end{Lemma}

\Proof
\begin{itemize}
\item For $p=0$ apply lemma~\ref{reg_L1} .
\item Let the lemma be true for $p-1$ .
\item Let $x$ be a point of $S(c_p)\setminus\Disp{\bigcup_{k<p}}S(c_k)$ and call $U$ the connected component which contains $x$ if one considers the partition $\R^2\setminus\Disp{\bigcup_{k<p-1}}S(c_k)$.\\
By lemma~\ref{reg_L1}, there are two connected components, $V$ and $W$, of $\R^2\setminus S(c_p)$ in the neighbourhood of $x$; $V$ and $W$ meet $U$ and so $U$ has at least two connected components in $\R^2\setminus\Disp{\bigcup_{k<p}}S(c_k)$.
\Demf
\end{itemize}

\medskip

\begin{Lemma} \label{reg_L3}
\mbox{ }
\begin{enumerate}
\item If an open segment $s$ is contained in the common boundary of two open connected polygons $O$ and $O'$, then the points outside and in the neighbourhood of $s$ are either in $O$ or in $O'$. The points which are in $O$ -- resp. $O'$ -- and close to $s$ are on the same ``side'' of the segment $s$.
\item If a closed Jordan curve $c$ is included in the common boundary of two open connected polygons $O$ and $O'$, then $S(c)=\partial(O,O')$.
\end{enumerate}
\end{Lemma}

\Proof 
\smallskip
\newline
1) Let $s$ be a segment of $\partial O\cap\partial O'$ which contains no tips, neither of $\partial O$, nor of $\partial O'$. Let $R$ be a rectangle with axis $s$. If this rectangle is not too thick one sees easily (see figure~\ref{fig_Recteps}) that there will be no other intersection than $s$ with the boundaries of $O$ and $O'$.\\
%-----proj_A-----
\begin{figure}[hbt]
  \begin{center}
  \begin{picture}(90,30)
    \thinlines
    \put(25,5){\framebox(30,10)[b]{${\scriptstyle s}$}}
    \put(28,18){\makebox(0,0)[br]{${\scriptstyle R}$}}
    \thicklines
    \multiput(15,10)(45,0){2}{\circle*{5}}
    \put(15,10){\line(1,0){45}}
    \put(25,10.5){\line(1,0){30}}
    \put(25,9.7){\line(1,0){30}}
    \put(15,10){\line(-3,-1){26}}
    \put(60,10){\line(1,2){9}}
  \end{picture}
  \end{center}
  \caption{The segment $s$ and the rectangle $R$ with $\partial O\cap\partial O'$.}
  \label{fig_Recteps}
\end{figure}
%---------------------

Let $R_1$ and $R_2$ be the two open connected rectangles of $R\setminus s$. They neither meet $\partial O$, neither $\partial O'$. So one of these rectangles, for example $R_1$, is included in $O$ and the other, in this case $R_2$, in $O'$. Indeed, both rectangles cannot be included in $O$ -- resp. $O'$ -- because they are disconnected and $O$ -- resp. $O'$ -- is conected.
\smallskip
\newline
2) The curve $c$ divides the plane into two connected components $U$ and $V$. So $O$ and $O'$ are included in $U$ and/or $V$. To show that they are not in the same connected component take an open segment $s$ as in 1). Then one shows in the same way that either $O$ meets $U$ and $O'$ meets $V$, and so $O\subset U$, $O'\subset V$, or we have $O'\subset U$ and $O\subset V$.\\
Therefore, $\partial(O,O')\subset\partial(U,V)=S(c)$ and since by assumption $\partial(O,O')\supset S(c)$, we get the announced result.
\Demf

\medskip

\begin{Lemma} \label{reg_L4}
Take an affine 1-normal segmentation $K$ and a connected component $O$ of $\Omega\setminus K$. Then $\partial O$ is a union of affine closed Jordan curves (i.e. polygons) and no pair of such polygons has a common segment.
\end{Lemma}

\Proof
\smallskip
\newline
\underline{1. step :} Let us recall and sketch the proof of an elementary result from graph theory. A non oriented graph is a couple $(X,U)$, where $X$ is a finite set and $U$ a symetric subset of $X\times X$. An element $(x,y)$ of $U$ is an edge of the graph with vertices $x$ and $y$. A graph is even if from every vertex an even number of edges start. A cycle of the graph $(X,U)$ is a sub-graph $(X',U')$ with $X'=\{x_1, x_2, \ldots , x_p=x_1\}\subset X$ and $U'=\{(x_1,x_2), (x_2,x_3), \ldots , (x_{p-1},x_1)\}\subset U$, where the $x_i, {\scriptstyle i\in\{1, \ldots , p-1\}}$ are all different. Using these definitions one has the following property : {\em Every even graph is a union of cycles having no common edges two by two.}\\
The proof is quite immediate. Construct recursively a first cycle using the fact that if an edge arrives at a vertice, then, as the graph is even, there exists another edge to quit this vertice. We get, as $X$ is finite, a finite chain of adjacent vertices which stops at one of the already scanned vertices. We extract a cycle $(X',U')$ and as $(X,U\!\setminus\!U')$ is an even graph, we iterate the process until no more edges are left over.
\medskip
\newline
\underline{2. step :} Let us show that the boundary of a region of the segmentation is an even graph. Take a tip of the boundary of $O$, put a circle around this tip such that there will be no other tips of $\partial O$ inside ( take the radius smaller than the length of the shortest segment ) . The disk defined this way is a union of angular sectors, separated  by segments of $\partial O$. Turning counterclockwise one sees that every second sector encountered belongs to $O$ wheras its adjacent sectors do not belong to $O$. Indeed, by 1-normality a segment of $\partial O$ cannot be inside $O$. Finally we get an even number of angular sectors and also an even number of segments arriving at the tip of $\partial O$.
\medskip
\newline
\underline{Conclusion :} Combining the first step with the second, we show that the even graph corresponding to the boundary of $O$ is a union of cycles, that means $\partial O$ is a union of polygonal closed Jordan curves having no common segment two by two.
\Demf

\medskip

\begin{Lemma} \label{reg_L5}Let $O$ be an open connected polygon. Within all the closed Jordan curves plotted in $\partial O$ there is one and only one which encloses $O$. We call it the ``external boundary of $\partial O$'' and it can be defined as the boundary of the unbounded connected component of $\R^2\setminus\partial O$. 
\end{Lemma}

\Proof As $O$ is bounded, there exists a unique unbounded component of $\R^2\setminus\partial O$, which we will call $U$. Notice that $\partial U\subset\partial O$.\\
Let us show that $\partial U$ is a closed Jordan curve. Anyway it contains a closed Jordan curve $c$ which divides $\R^2$ in two connected components $V$ and $W$, the second being unbounded. As $O$ and $U$ are connected one has $O\subset V$ and $U\subset W$, and so $\partial(U,O)\subset S(c)$.\\
From this we conclude that $\partial U=\partial U\cap\partial O=\partial(U,O)\subset S(c)$ and therefore $\partial U=S(c)$.
\Demf 

\medskip

\begin{Lemma} \label{reg_L6}
Let $K$ be a an affine 1-normal segmentation and $c$ a closed Jordan curve, with $S(c)\subset K$. Suppose the bounded connected component defined by $c$, which we will denote $O$, contains exactly two regions, $O'$ and $O''$, of the segmentation. Then $\partial(O',O'')$ is a Jordan curve with all its interior points included in $O$. 
\end{Lemma}

\Proof 
\smallskip
\newline
\underline{1. step :} Every segment $s$ of $\partial O$ is in the boundary of only one of the open regions $O'$ and $O''$. This follows immediately from lemma~\ref{reg_L3} (1) .
\medskip
\newline
\underline{2. step :} $\partial O'\cap\partial O''$ is connected.\\
By the first step every  segment of $\partial O'\cap\partial O''$ has its interior points included in $O$. Let us suppose by contradiction that two points of $O$, $x$ and $y$, are in two distinct connected components of $\partial O'\cap\partial O''$.\\
For each of these connected components one has the following: either it contains a closed Jordan curve, included entirely in $O$, or it contains a curve with tips on $\partial O$ which we close with a curve of $\partial O$ in order to get a closed Jordan curve. In both cases we get two Jordan curves $c'$ and $c''$ not contained in $\partial O$ and verifying $S(c')\cap O\neq S(c'')\cap O$.\\
The three Jordan curves $c$, $c'$ and $c''$ verify the conditions of lemma~\ref{reg_L2} and define therefore four connected components of the plane. This is in contradiction with the hypothesis that the boundaries of $O$, $O'$ and $O''$ just define three connected components : $O'$, $O''$ and the complementary part of $\Adh{O}$.
\medskip
\newline
\underline{3. step :} $\partial O'\cap\partial O''\cap O$ contains no geometrical crossings.\\
If there was such a geometrical crossing $x$, the, at least, three segments forming the crossing  would be included in at least two closed Jordan curves of $\partial O'\cap\partial O''$, distinct in $O$. This is the situation encountered in the second step which yielded a contradiction.
\medskip
\newline
\underline{Conclusion :} The three steps show that $\partial O'\cap\partial O''\cap O$ is connected and without geometrical crossings. Thus it is a polygonal Jordan curve.
\Demf

\medskip

\begin{Lemma} \label{reg_L7}
Take an affine 1-normal segmentation $K$ having more than one region, then there are two regions enclosed, $O$ and $O'$, such that $\partial(O,O')$ is a Jordan curve.
\end{Lemma}

\Proof We will construct recursively a series of closed Jordan curves. The curves will be constructed such that $S(c_{n+1})$ is included in the closure of the open set enclosed by $c_n$, $O_n$, and $c_{n+1}$ different from $c_n$.\\
The first curve will be $c_0=\partial\Omega$, the boundary of the picture. We will stop the construction if there remains a Jordan curve enclosing exactly two regions of the segmentation, or if there remains a Jordan curve which is the boundary of two regions of the segmentation. In both cases the proof will be complete, either immediately, or by applying lemma~\ref{reg_L4} .
At level $n-1$ denote by $c$ the closed Jordan curve and by $O$ the open set enclosed by $c$. If $c$ does not enclose exactly two regions of the segmentation there are two cases we have to consider :
\begin{enumerate}
\item There exists a closed Jordan curve $c'$ contained in $\Adh{O}$ and distinct from $c$, which encloses more than one region. We take this curve $c'$ to continue the recurrence.
\item Every closed Jordan curve $c'$ contained in $\Adh{O}$ and distinct from $O$, encloses exactly one region of the segmentation. There are again two possibilities :
\begin{itemize}
\item One of these Jordan curves $c'$ meets $\partial O$ . We take a connected part of $S(c')\cap O$; this defines a Jordan curve meeting $\partial O$ in two points $x$ and $y$. We extend this curve with the arcs $\stackrel{\frown}{xy}$ and $\stackrel{\frown}{yx}$ included in $\partial O$. We do this in order to get two closed Jordan curves $c_1$ and $c_2$ which are contained in $\Adh{O}$ and distinct from $\partial O$ . So each enclosing exactly one region of the segmentation and $S(c_1)\cap S(c_2)$ being connected, we stop the iteration.\\
If $x=y$ we would have one of the $S(c_i)$s equal to $\partial O$, which is impossible in case 2) .
\item No curve $c'$ meets $\partial O$; denote by $O'$ the region enclosed by $c'$.\\
Thus $c'$ meets only one other boundary of a region $O''$ and we have finished :\\
 $S(c')\subset\partial O'\cap\partial O''$ and so by lemma~\ref{reg_L3} $S(c')=\partial O'\cap\partial O''$ .\\
Every $c'$ meets more than two boundaries of regions (i.e. $c'$ meets in fact three regions ). We have at least one geometrical crossing in $O$ and so at least two distinct Jordan curves $c_1$ and $c_2$, which enclose $O_1$ and $O_2$. Let $c_e$ be the external boundary of $O_1\cup O_2$ : it is a Jordan curve distinct from $c$ and enclosing at least two regions. This is in contradiction with the hypothesis.
\Demf
\end{itemize}
\end{enumerate}

\medskip

\begin{Lemma} \label{reg_L8}
Let $K$ be an affine 1-normal segmentation with $\alpha$ regions. Then $K$ is the union of $\alpha-1$ affine Jordan curves having no common segments.
\end{Lemma}

\Proof Let $c_1$ be an affine Jordan curve as given  by lemma~\ref{reg_L7} . Let us define a new segmentation $K_1$ obtained by removing the segments of $c_1$. We merge exactly two regions of $K$. The segmentation $K_1$ is also affine and 1-normal, so we can iterate the process and define a series of segmentations $K_i$ such that every segmentation has a region less than the preceding one and has been obtained by removing an affine Jordan curve. The process stops if there is only one region left, $\Omega$.
\Demf

\medskip

\begin{Lemma} \label{reg_L9}
Let $\alpha$ be the number of regions of an affine 1-normal segmentation, $\beta$ the number of geometrical curves and $\gamma$ the number of geometrical crossings. Then
$$\gamma\leq2\cdot(\alpha-1)\;\mbox{ and }\;\beta\leq3\cdot(\alpha-1)-2\;\;.$$ 
\end{Lemma}

\Proof Consider the proof of the preceding lemma (\ref{reg_L8}). The curve $c_1$ contains at most two geometrical crossings of $K_1$ : its tips if it is an open Jordan curve. So passing from $K=K_0$ to $K_1$ eliminates at most two geometrical crossings. By iterating the process the first inequality follows.
\medskip

Let us now analyse how the number of geometrical curves decreases when passing from $K_0$ to $K_1$. If $c_1$ is a closed Jordan curve it is the only geometrical curve to disappear.\\
If $c_1$ is an open Jordan curve there are two geometrical crossings at its tips. If one of these crossings meets more than four segments of $K$ the other geometrical curves are not modified. But if there are only three segments at this crossing it will vanish when $c_1$ is removed and the other two geometrical curves will merge into one.\\
Removing $c_1$ decreases $\beta$ of at most 3 and iterating the process yields the second inequality.
\Demf

\medskip


\section[Propri\'et\'es des segmentations obtenues par croissance de r\'egions]{Properties of segmentations obtained by merging.}
\label{reg_ssec_P}

\medskip

\begin{Lemma}\label{regN_L1}
Let $(u,K)$ be a 2-normal segmentation. Then every pair of regions $O$ and $O'$ verifies
$$\ell(\partial(O,O'))\leq\frac{\osc(g)^2}{\lambda}\cdot\min(|O|,|O'|)\;,$$
where $\osc(g)= \sup(g)-\inf(g)$ is the oscillation of $g$.
\end{Lemma}

\Proof Let $K'=K\setminus\partial(O,O')$. By 2-normality we have
$$0\leq E(K')-E(K)=\int_{O\cup O'}(u_{ij}-g)^2-\int_O(u_i-g)^2-\int_{O'}(u_j-g)^2-\lambda\ell(\partial(O,O')),$$
with $u_i$, $u_j$ and $u_{ij}$ being the mean values of $g$ on $O$, $O'$ and $O\cup O'$. We get, supposing for example that $|O|\leq|O'|$,
\begin{eqnarray*}
\lambda\cdot\ell(\partial(O,O'))&\leq&\int_O\left[(u_{ij}-g)^2-(u_i-g)^2\right]\\
 & \leq & \min(|O|,|O'|)\;\osc(g)^2 \mbox{ \Demf}
\end{eqnarray*}

\medskip

\begin{Lemma}\label{regN_L2}
For every region  $O$ of a 2-normal segmentation, denote by  $N(O)$ the number of neighbouring regions. Then
$$N(O)\geq \frac{C\lambda}{\sqrt{|O|}\; \osc(g)^2}\;,$$
where $C$ is the isoperimetric constant in  $\Omega$.
\end{Lemma}

{\em Proof.}  Call $O_j$ a neighbouring region of $O$.   The fact that $O$ and $O_j$ cannot be merged without increasing the energy $E$ implies that
$$\lambda\,\ell\left(\partial\left(O, O_j\right)\right)\leq |O|\;\osc(g)^2.$$
Thus by adding these inequalities for all neighbours of $O$, we obtain
$$\lambda\,\ell(\partial O) \leq N(O)|O|\;\osc(g)^2. $$
We conclude by applying to $O$ the isoperimetric inequality in $\Omega$.\Demf

\medskip

\begin{Lemma}\label{regN_L3}
Let $\alpha$ be the number of regions of a 2-normal affine segmentation. Then
$$\alpha\leq\frac{288\,|\Omega|\;\osc(g)^4}{C^2\lambda^2}\;.$$
\end{Lemma}

\Proof The union of all regions $O_i$ is equal to the rectangle $\Omega$ and therefore $\Disp{\sum_i} |O_i| = |\Omega|$. Thus the number of $O_i$ verifying $|O_i| \leq \Dfrac{2}{\alpha}\,|\Omega|$ is greater than  $\Dfrac{\alpha}{2}$.
\smallskip
\newline
Let us now apply lemma~\ref{regN_L2} to all of these $O_i$s.  Each one of them has at least
$$\frac{C\lambda}{\sqrt{|O_i|}\;\osc(g)^2} \geq C\lambda\cdot\sqrt{\frac{\alpha}{2\,|\Omega|}} \cdot\frac{1}{osc(g)^2} $$
  neighbouring regions.  Consequently the number $\beta$ of common boundaries, and therefore of edges, verifies
$$ \beta\geq\frac{\alpha}{4} \cdot C\lambda\;\sqrt{\frac{\alpha}{2\,|\Omega|}}\cdot \frac{1}{\osc(g)^2} = C\lambda2^{-\frac{5}{2}}\cdot \frac{\alpha^\frac{3}{2}}{\sqrt{|\Omega|}}\cdot\frac{1}{\osc(g)^2}\;.$$
 By lemma~\ref{reg_L9}, we have
$$\beta \leq 3\alpha,$$
this implies that
$$C\lambda2^{-\frac{5}{2}} \;\frac{\alpha^\frac{3}{2}}{\sqrt{|\Omega|}\,\osc(g)^2}\leq 3\alpha $$
and thus we obtain 
$$\alpha \leq \frac{288\,|\Omega|\;\osc(g)^4}{C^2\lambda^2}\;.\;\mbox{  \Demf}$$

\medskip

\begin{Remark} This is the same estimate (with a bigger constant) than in Mumford and Shah~\cite[Th.5.2]{MumS2}. However, in the mentioned paper, this estimate is obtained for a global minimum.  The fact that we get this estimate in the case of 2-normal segmentations indicates an analogy of structure between global minima and this kind of local minimum.
\end{Remark}

Let us state the main theorem of this chapter.

\begin{Theorem} \label{th_compact}The set of 2-normal affine segmentations has the following compactness property : for every sequence $K_n$ of such segmentations, there exists a subsequence  converging to a segmentation $K$ such that
$$E(K) \leq\liminf_n E(K_n).$$
$K$ is not necessarily 2-normal, but has anyway a 2-normal subsegmentation with still less energy.
\end{Theorem}

\subsubsection*{Comments.}

This result may seem to be weak, since one generally hopes to get for a given problem a unique solution, or at least a finite number of solutions.  However, we already know that our problem may have infinitely many local minimizers, and therefore the unique restriction which we can hope to obtain for a given set of ``solutions'' to our problem is compactness.\\
Compactness is a (very) weak form of uniqueness : it indicates that the set of 2-normal segmentations is much smaller than the set of all possible segmentations (which is not compact).\\
It also provides a very important computational property : If we define an algorithm  computing better and better solutions for our problem, that is solutions with decreasing energy, we know that these solutions must accumulate around a solution better than everyone.  Since one can, by the axiom of choice, find at least one minimizing sequence for the energy $E$, the theorem~\ref{th_compact} provides a very simple existence proof for global or even local minimizers.  However, we don't know how to construct explicitly and quickly a globally minimizing sequence.  Thus the practical interest of theorem~\ref{th_compact}, as we shall see, is to provide a way of controlling more general minimizing sequences, not necessarily tending to a global minimum of the functional.\\
One can prove (\cite{MorS2}) that the above properties are specific of the dimension 2.  In dimension 3, 2-normal segmentations make no compact set, and one needs the full normality assumption to restore this compactness.  Thus region growing algorithms based on recursive merging seem to be inconsistent in dimension greater than 2.

\begin{flushleft}
{\em Proof of theorem~\ref{th_compact}.}
\end{flushleft}

The proof of the announced compactness property is essentially  based on the fact that the number of edges of any 2-normal segmentation is now bounded from above by the preceding estimates (cf. lemmas~\ref{reg_L9} and \ref{regN_L3}). By the Ascoli-Arzela theorem, each one of the edges  can be supposed to converge to a limit edge if we extract an ad hoc subsequence.  The limit segmentation is then defined by these limit edges.  By passing to the limit, neither the integral part of the  energy nor the length of the edges can increase, and therefore this limit segmentation has an energy smaller than the inf limit of the energies of the sequence.  For more (technical) details see~\cite{MorS1}.\Demf
\medskip

\begin{Remark} \label{reg.rem_elsr}{\bf : Elimination of small regions.}\\
It is easy to deduce from the preceding proof a lower bound on the  area of each region of the segmentation.  Indeed, take any region $O$ of the segmentation.  By Lemma~\ref{regN_L2}, the number of neighbouring regions $O_j$ is at least
$$N(O)\geq \frac{C\lambda}{\sqrt{|O|}\;\osc(g)^2}\;.$$
Thus the number $\alpha$ of regions of the segmentation is at least
$$\frac{C\lambda}{\sqrt{|O|}\;\osc(g)^2}\;.$$
By using the upper bound for $\alpha$, given in lemma~\ref{regN_L3} we get 
$$\frac{288\,|\Omega|\;\osc(g)^4}{C^2\lambda^2} \geq \frac{C\lambda}{\sqrt{|O|}\;\osc(g)^2}\;.$$
Thus the area of $O$ is bounded from below by a positive constant only depending on $g$, $\lambda$ and $\Omega$.   Therefore a merging method based on the minimizing of the energy $E(K)$ will spontaneously eliminate the small regions.
\end{Remark}
\medskip

\begin{Remark} \label{reg.rem_eltr}{\bf : Elimination of thin regions.}\\
It is also easy to deduce  from the above estimates that the regions are not too ``thin'', that is, verify an ``inverse isoperimetric inequality''.  Indeed, each region $O$ verifies for a constant $C$  depending only on $g$ and $\Omega$,
$$|O|^\frac{1}{2} \geq C\cdot \ell(\partial O)\;.$$
  This last result can be deduced from remark~\ref{reg.rem_elsr}, since the surface of $O$ is bounded from below and $\ell(\partial O)$ from above (as the length of the segmentation is under control).  The estimate obtained can be proved with a better constant $C$ (see~\cite{MorS1}).  Thus the devices based on the elimination of thin regions (see~\cite{PapJ}) for instance, and many clustering algorithms~\cite{Pav2}) can be considered as implicit in the search of an optimal 2-normal segmentation.
\end{Remark}
\medskip

\begin{Remark}{\bf : Smoothing of the boundaries.}\\
The 2-normal segmentations have no chance of having boundaries smooth everywhere.  However, since their length is under control, a classical geometric measure theory (see for example \cite[th.14.3]{Si-L}) asserts that they are almost everywhere $C^1$.  Thus the presence of noise, for instance, can alter the regularity of these boundaries but not make them increase indefinitely, as it is the case for some region growing devices.  What can be done in order to restore this regularity and how can such a regularization device be deduced from the energy to be minimized ? \\
The answer is in relation~\Pref{MS_curv}, which asserts that the curvature of an energy minimizing boundary is controlled.  This equation shows that the length term of our ``simplest energy'', coupled to its bidimensional contrast measuring term, is enough to ensure that the boundaries are analogous to snakes.  They tend to keep at places where $g$ has a jump and they remain smooth, since from the bound on the curvature follows a bound on the first derivative~\cite{MorS1}.  The merging of regions (with the subsequent smoothing of the spline $u$), should therefore be completed by a merging of the boundaries in the same sense : imposing therefore that this boundary is smoothed according to the criterion on curvature imposed by the energy.  This idea is implicit in~\cite{PavL}.  As noticed by these last authors, that imposes to treat region boundaries like snakes, but the relation~\Pref{MS_curv} proves that still this tool can be deduced from the ``simplest energy'' that we have considered.
\end{Remark}


\section[Un algorithme pyramidal construisant une segmentation affine 2-normale]{A pyramidal algorithm constructing 2-normal affine segmentations.}

We now consider the problem of defining and computing a 2-normal  segmentation.  Notice that not all 2-normal segmentations are interesting : for instance, the empty segmentation, where $\Omega$ is the single region is clearly a 2-normal segmentation.  If the scale parameter $\lambda$ is very large, it is also a reasonable segmentation since one ``pays'' a too large energy amount for having any boundary.  However, it is obvious from the definition that the empty segmentation is 2-normal for every $\lambda$, which certainly proves that the assertion that a segmentation is 2-normal is not enough to ensure that it is ``good''. But if we follow the main idea of the region growing methods~\cite{Zu1}, {\em we shall see that what they compute is precisely a 2-normal subsegmentation of a fine initial segmentation, obtained by recursive merging}.
\medskip

Assume that the datum $g$ is defined on a rectangle.  This rectangle is divided in small squares of constant size (the pixels) and $g$ is assumed to be constant on each pixel.  Here are the properties which we require for the segmentations computed by a region growing algorithm, defined as an application associating to $g$ and $\lambda$ a segmentation $(u, K)$.
\begin{description}
\item[a)] ``Correctedness'' (Fixed point property) : Assume that $g$ is piecewise constant on some areas of the rectangle. Then there exists a value $\lambda_0$  of the parameter $\lambda$ such that for every $\lambda<\lambda_0$, the segmentation $(u,K)$ obtained by the algorithm verifies $u=g$ and $K$ is the union of the boundaries of  the areas where $g$ is constant. This property has been proved to be asymptotically true for the segmentations which are global minima of the energy $E$ as $\lambda$ tends to zero~\cite{Ric}.  But we impose it here as a nonasymptotic property. 
\item[b)] ``Causality'' (Pyramidal segmentation  property) : If $\lambda>\lambda'$, then the  boundaries provided by the algorithm for $\lambda$ are contained in those obtained for $\lambda'$ and the areas of the segmentation associated to $\lambda$ are the unions of some of the areas obtained for $\lambda'$.
\end{description}
The last property ensures that a fast pyramidal algorithm can be implemented, computing a hierarchy of segmentations from fine to coarse scales. Moreover the coarser segmentation will be deduced from the finer by ``merging'' operations, with a pyramidal structure for the computation.  Note that, as a consequence of the fixed point property, if $\lambda$ is very small, the computed segmentation is attained with $(u_0,K_0)$ where $u_0=u$ and $K_0$ consists of all the boundaries of all the pixels, and therefore coincides with the global minimum as $\lambda$ is zero. We shall call this segmentation, where each pixel is a region, the ``trivial segmentation''.  The recursive merging algorithm which we use verifies all the above mentionned properties.

\section[Conclusion]{Conclusion.}
In this chapter, we have proved that the minimizing of the ``simplest''  segmentation energy  entails the implicit realization of properties sought by most segmentation devices.  Indeed, the most primitive segmentation tool, the ``merging'', applied to the simplest possible segmentation energy, is enough to ensure a small ( compact ) set of possible segmentations, with no small regions and no thin regions. Uniform a priori estimates for the size and number of the regions can be given for all segmentations obtained by exhaustive ``merging''.  Moreover, the region growing method associated to the recursive merging is enough to retrieve all piecewise constant functions.  Such a merging method is not accurate enough to obtain smooth boundaries,  but it controls anyway their length. The big advantage of this method is its velocity. 
\smallskip

We do not pretend that minimizing such an energy is enough to characterize good segmentations.  We only assume, and tried to justify here, that it is a necessary step.  The following would be to define directly evolution equations generating boundaries and regions.  Such an evolution equation is implicit in the region growing algorithms, which are therefore close to the nonlinear evolution equation proposed by Malik and Perona for edge detection~\cite{MaliP1}. In our opinion, the correct formalization of such an evolution equation is a good challenge.
