Ce chapitre a \'et\'e \'ecrit en collaboration avec Jean Michel Morel.

\skipaline

\skipaline


{\small {\noindent \bf Abstract.} 
  In this paper \footnote{Conference held at Trento, July 92.
 To appear in proceedings on "Surface Tension and Movement by Mean Curvature".
 De Gruyter Publishers (Berlin).}, we first prove that, under four simple axioms, 
the multiscale analysis of shapes is given by a curvature motion equation. 
 In a second part, we illustrate the advantages of such an axiomatic analysis
 to discuss a psychophysical theory of early vision due to B. Julesz : 
 the texture preattentive discrimination theory. The result was unexpected: We prove that the Julesz
axiomatic is {\it too good} for human vision and leads to a hyperdiscrimination
algorithm.}   

\skipaline

\section [Introduction.]  {Introduction.}

 
\rm Shape analysis methods try to extract from digital shapes 
local geometric "features" like holes, corners, orientation, inflexion points ... 
on which a further "intelligent" analysis could be based.  
In order to extract such features, the local analysis implies intuitively 
that one should use differential operators. 
 However, because of perturbations due to the nature of the picture 
as well as to the recording conditions, pure differential operators 
are completely unreliable.  Therefore, the vision research has defined
 as a paradigm the concept of {\it multiscale analysis}. 
 Multiscale analysis aims at a smoothing of the shape. 
  This smoothing allows the reliable extraction of local and semilocal features,
 but introduces a scale parameter, $t$, 
which measures the loss of locality (and the win in globality)
 of the extracted features, see [Koe], [Wit], [MaMo], ... 
 We shall prove that, under a simple list of obvious axioms,
 the multiscale shape analysis is given by a curvature motion equation.
 In a second part of this conference, we shall show numerical experiments 
illustrating the advantages of such an analysis to discuss a theory 
of early vision due to B. Julesz : 
{\it the texture preattentive discrimination theory}. 
 We shall see that this theory is formalized 
by a curvature motion and can be discussed in this framework.
  In particular, we shall see that the Julesz {\it texton theory} is "too good" as a model 
for the human perception. Indeed, we prove that a formal multiscale analysis
 based on this model must be a curvature motion, and achieves "hyperdiscrimination" 
of textures which should be undiscriminable for Julesz theory.

In section 2, we state the four principles of shape analysis. In section 3,
 we prove that they lead to a single special curvature motion. Section 4 is devoted
to the generalization of the model for image processing. In section 5, we present 
the Julesz axiomatic of texture discrimination. Section 6 gives a translation of
Julesz axioms into a mathematical theory and section 7 gives numerical results
on Julesz textures.

\skipaline

\section [The four principles of Multiscale Shape Analysis.]{ The four principles of Multiscale Shape Analysis.}


\begin{figure} [htb]
  \insertps{pyramide.ps} {100mm}{20mm}
\end{figure}


\skipaline

Define a shape or silhouette as a closed set X whose boundary is a Jordan curve of $\Re ^2$. 
 We denote by $T_t(X)$  the {\it shape analysed at scale} $t$. $X$ is identified with its
characteristic function $X(x)=1$ if $x \in X$ and $0$ else.  
We call multiscale analysis any family operators $(T_t)_{t \ge 0}$ acting on shapes
and we set $X(t)=T_t(X)$. 
  
\skipaline


\rm We first consider a principle which is called in vision theory
  the {\it pyramidal architecture} property.
  According to this assumption, $T_t$ can be computed from $T_s$  for any
  $s\le t$ and $T_0$ is of course the identity. 
 This is natural, since a coarser analysis of the original picture is 
likely to be deduced from a finer one without any dependence upon the
 original picture.  Of course the finest picture analysis is the identity.
   In order to formalize the pyramidal architecture we include $T_t = T_{t,0}$ 
into a family of {\it transition operators} $T_{t,s}$ 
 indexed by $0 \le s \le t$  and satisfying 

{\noindent \bf [Pyramidal architecture]} \hspace{1cm} $T_{t+s} = T_{t+s,s}T_s$ for all $0 \le s$, $ 0 \le t$

\skipaline


\rm  The shape analysis process is thought of as a flow of the shape 
through different filters, each associated with a scale $t$. If we discretize
 such a process, it yields a serie of operators
 $S_n = T_{(n+1)h,nh} $ applied successively.   

 

\skipaline


\rm Assume that $X$ and $Y$ are two silhouettes and that for some
 $x \in \partial Y$ and some $r>0$,
 one has $X \cap B(x,2r) \subset Y\cap B(x,2r)$.
  Assume further that the inclusion is strict in the sense that
 $\partial X$ and $\partial Y$ only meet eventually at $x$.
  Then we shall say that {\it the shape} $X$ {\it is included in shape} $Y$ {\it around} $x$.

\skipaline

{\noindent\bf [Shape local inclusion]}  If $X$ is included in $Y$ around $x$,
 then for $h$ small enough, $T_{t+h,t}(X) \cap B(x,r) \subset T_{t+h,t}(Y)\cap B(x,r)$.



\skipaline

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


\skipaline




This last axiom implies that the value of $T_{t+h,t}(X)$ for $h$ small,
 at any point $x$, is determined by the behaviour of $X$ near $x$.
  We are allowed to take $r$ infinite.
   Therefore the shape local inclusion principle also implies that if
 a shape is globally contained in another, this order is preserved for every scale [MaMo].
 Notice that the combination of both pyramidal and shape local inclusion principles
is generally called in Image Processing {\it causality} 
[Koe], [Wit], [Kim], [SaTa], [KTZ].
Indeed, the causality assumption in Image Processing states that when the
scale increases, no new structure appears in the image.

\skipaline

Both preceding principles allow, as we shall see,
 to localize the shape analysis in space and time and we therefore only need
 to state what the multiscale analysis makes of very simple shapes in order
 to specify it.  So we add a basic "principle" which will state what happens
 to disks.   As we shall see, disks are somehow the "basis" on which every
 shape can be decomposed.

\skipaline



{\noindent\bf [Basic principle]} \rm Let $D=D(x,1/r)$ be a disk with curvature $1/r$ and center $x$.
  Then $T_{t+h,t}(D)$ is a disk with radius $\rho (t, h,1/r ) $ and center $x$.
  Moreover, the function $h \rightarrow \rho(t,h,1/r) $ is differentiable with
 respect to $h$ at $h=0$ and the differential is continuous with respect to $1/r$.

\skipaline

The "basic principle" implies that the multiscale analysis behaves
 in a smooth and isotropic way. 

\skipaline 

In the following, we set $$g(t, 1/r) = \frac{\partial \rho}{\partial h}(t, 0, 1/r)$$
\rm Note that $g(t,s)$ is defined for $t \ge 0$ and $s \in \Re $, now to define
$g(t,0)$ we must assume that $lim \; g(t,1/r)$ exists when $r$ tends to $+\infty $ or $-\infty $ .
 The radius $r$ may be positive or negative, according to the orientation of the normal $\vec n(x)$.
 In the case where the curve is a Jordan curve enclosing a set $X$,
 we take as a {\it convention that} $\vec n(x)$ is {\it pointing outside} $X$ and {\it the curvature
 is negative if} $X$ {\it is convex at} $x$, {\it positive else}.
It may seem natural to assume therefore that $g(t,\kappa )$ is odd with respect to $\kappa $.
Indeed, this corresponds to the assumption that a black disk on grey background and
a white disk behave in a same way. 
 


\skipaline
 
{\noindent \bf Lemma 1.}{\it  The function $g(t, \kappa) = \frac{\partial \rho}{\partial h}(t,0,\kappa)$
 is nondecreasing with respect to $\kappa$.}

\skipaline

\begin{figure} [htb]
  \insertps{disque.ps} {40mm}{30mm}
\end{figure}


\skipaline




  \rm Consider two disks $D$ and $D'$ with respective radii $\vert r \vert$ and $\vert r'\vert >\vert r\vert$ 
and keep in mind the above convention about the orientation. So we have algebraically: $r'<r$ and $\kappa < \kappa '$.
  Let $D$ be included in $D'$ and tangent to $D'$ at some point $x$. 
 By the shape local inclusion principle $T_{t+h,t}(D)$ is contained in
 $T_{t+h,t}(D')$.   By the basic principle both sets are disks concentric
to $D$ and $D'$ respectively and with radii $\rho (t, h,\kappa) $ and 
$\rho (t, h,\kappa ') $.  The inclusion of both disks therefore yields
 $$\rho (t, h, \kappa) -\rho (t, 0,\kappa ) \le \rho (t, h, \kappa ') -\rho (t, 0,\kappa ')$$
  Dividing by $h$ and passing to the limit when $h$ tends to $0$ yields the result.

\skipaline


The next optional shape preserving principle is the affine invariance of shape analysis.
  Set $AX(x) = X(Ax)$ for any linear map $A$. The affine invariance can be stated as:

\skipaline

{\noindent \bf [Affine inv.]} \rm For any A and $t \ge 0$, there exists a $C^1$ function $t'(t,A) \ge 0$ such that
 $AT_{t'(t,A),t'(s,A)}=T_{t,s}A$. Moreover, the 
function $\phi (t)=\frac{\partial t'}{\partial \lambda}(t,Id)$ is positive for $t>0$.
 
\skipaline

\rm This relation means that the result of the multiscale analysis $T_t$ is
 independent of the size and position in space of the analyzed features : 
this is very important in the world where we live,
 since the same plane object $X$ can be seen at very different distances and
 orientations and therefore with any affine change $X(x) \rightarrow X(Ax)$.
 A linear map corresponds to the anamorphosis of a plane image when it is presented to
the eye at an arbitrary distance and with an arbitrary orientation in space.
 
  
\skipaline


{\noindent \bf Lemma 2.} [AGLM]{\it (Normalization of scale)}
\noindent {\it Assume that $t \rightarrow T_t$ is a one to one family of operators
verifying [affine invariance]. }


\noindent {\it  Then the funtion $t'(t,B)$ only depends on $t$ and $\vert detB \vert$:  
$t'(t,B)=t'(t,\vert detB\vert^{1/2})$ and is increasing with respect to $t$.}

\noindent {\it Moreover, there exists an increasing differentiable rescaling function 
$h: [0, \infty ] \rightarrow  [0, \infty ]$, such that 
$t'(t,B)=h^{-1}(h(t)\vert detB\vert^{1/2})$ and if we set $S_t=T_{h^{-1}(t)}$
we have $t'(t,B)=t\vert detB{\vert}^{1/2}$ for the rescaled analysis.}

\skipaline

{\noindent \bf Remarks.}

\noindent \rm a) Thus for any multiscale analysis, we can normalize the scale-space 
relation and give a spatial interpretation to $t$ under a simple rescaling.

\noindent b) The assumption on $t'$, $\phi (t)=\frac {\partial t'}{\partial \lambda}(t,Id) > 0$, 
can be interpreted by looking at the relation $AT_{t'}=T_tA$
when the scale $\lambda =\vert detB\vert^{1/2} $ increases, i.e when the image
is shrinked before analysis by $T_t$. Then, the corresponding analysis
time before shrinking is increased. In more informal terms we can say that
the analysis time increases with the size of the picture.


\skipaline

The proof of the lemma 2 is given in [AGLM] and in appendix.


\skipaline


\section  [The fundamental equation of Shape Analysis.]{The fundamental equation of Shape Analysis.}

 \rm  When a point $x$ belongs to an evolving curve, we denote by
 $\dot {x}$ the time derivative of $x$,
 which is a vector of $\Re ^2$.  By $curv(x)$ we denote the curvature
 of a curve which is $C^2$ at $x$. Recall that the curvature is defined
 as the inverse of the radius of the osculatory circle to the curve at $x$.
  The curvature is zero if the radius is infinite.
  By $\vec n(x)$ we denote the vector normal to the curve.
  In the case where the curve is a Jordan curve enclosing a set $X$,
 we take as a {\it convention that} $\vec n(x)$ is {\it pointing outside} $X$ and {\it the curvature
 is negative if} $X$ {\it is convex at} $x$, {\it positive else}.

\skipaline 

{\noindent \bf Theorem 1.} {\it (i) Under the  three principles (pyramidal, local shape inclusion,
 "basic"), the multiscale analysis of shapes is governed by the 
 curvature motion equation
 $$ \dot{x} = g(t, curv(x)) \vec n(x) \eqno(1) $$ 
 where $g$ is defined in lemma 1.

\noindent (ii) If we assume [Affine inv.], 
then the equation of the multiscale analysis is, up to rescaling:
$$ \dot{x} = \gamma (t.curv(x)) \vec n(x) \eqno(2)$$
where $\gamma$ is defined as following:
$\gamma (x)=a.x^{1/3}$ if $x\ge 0$ and $\gamma (x)=b.x^{1/3}$ if $x\le 0$     
and $a$, $b$ are two nonnegative values.

\noindent (iii) If we add that $T_t(X^c)=T_t(X)^c$ [Reverse contrast invariance] 
then the function $g$ in (i) is odd and $a=b$ in (ii).
 }
  
\skipaline

\rm By the expression "governed by", we mean that the equation must be verified 
at any point $(t,x)$ of $X(t)$ where the silhouette is smooth enough to give a classical
 sense to both terms of the equation.

\skipaline

{\noindent \bf Remark:} \rm
It has been proved [GaHa], [Gra], [Ang] that the equation (1)
 with $g(t,s)=s$ has smooth solutions.
This equation has been introduced in picture processing by [KTZ],
 [MaMo] and [AGLM] in different contexts.
 An early version of an algorithm leading to equation (1) in [KoDo]. 

\skipaline

The equation (2) has been introduced and axiomatically
justified (with a more complicated axiomatic however) in [AGLM].
It has also been proposed in [SaTa].  
Existence and regularity of the solution are proved in [SaTa].


\skipaline

  
\noindent (i) Let $X$ be a silhouette and assume that $T_t(X)$ has a boundary which is a $C^2$
 manifold in a neighbourhood of a point $x$ of $\partial X$.
  Then it has a curvature $\kappa$ at point $x$ and we consider a subosculatory and
 a surosculatory disk, that is, a disk $D$ with curvature $\kappa -\epsilon $ and a disk
 $D'$ with curvature $\kappa+\epsilon $, both tangent to the silhouette at $x$. 
   Applying the same two principles as in the lemma, we see that 
$$T_{t+h,t}(D)\cap B(x,r) \subset T_{t+h,t}(X) \cap  B(x,r) \subset T_{t+h,t}(D')\cap B(x,r) $$
  Thus, denoting by $x(t+h)$ the point of $\partial T_{t+h}(X)$
 such that $x(t+h) -x(t)$ is parallel to $\vec n(x)$, we obtain
$$\rho (t, h, \kappa- \epsilon ) -\rho (t, 0, \kappa -\epsilon ) \le (x(t+h)-x(t)).\vec n(x) \le \rho (t, h,\kappa +\epsilon ) -\rho (t, 0,\kappa +\epsilon )$$
  Dividing by $h$ and passing to the limit when $h$ tends to $0$
 yields $$\frac{\partial \rho}{\partial h}(t,0,\kappa -\epsilon) \le \liminf \frac{x(t+h)-x(t)}{h}.\vec n(x) $$
$$ \limsup \frac{x(t+h)-x(t)}{h}.\vec n(x) \le \frac{\partial \rho}{\partial h}(t,0,\kappa +\epsilon)$$
We obtain equation (1) by passing to the limit when $\epsilon $ tends to $0$ and using the fact that
 $\kappa \rightarrow \frac{\partial \rho}{\partial h}(t,0,\kappa )$ is continuous.

\skipaline


\noindent (ii) After renormalization, we can use the identity
$$ T_{t+h,t}D_{\lambda }=D_{\lambda }T_{(t+h)\lambda ,t\lambda}$$
(where $D_{\lambda}=\lambda Id$) and so, we can deduce that
the function $\rho$ of the basic principle must verifye
$\rho (t,h,\frac {\lambda}r)=\frac 1{\lambda}\rho(\lambda t,\lambda h,1/r)$ 
Therefore, we obtain the relation (after differentiation with respect to $h$ at $0$)
$$g(t,\lambda s)=g(\lambda t,s)$$ for any $t>0$, $\lambda >0$ and $s \in \Re$
Changing $t$ in $t/ \lambda $ and taking $\lambda =1/t$ we get $g(t,s)=g(1,ts)=\beta (ts)$
for the function $\beta$ defined as $\beta (x)=g(1,x)$.

\skipaline

\noindent (iii) After renormalization, we can use the identity 
$T_{t+h,t}A=AT_{t+h,t}$, where $A$ is the linear transform whose determinant is one
$$(x,y) \rightarrow ({\lambda} x,(1/{\lambda}) y) \; \; \lambda>0$$
Let us apply this identity to the unit disk $\Delta$. Look at the point
$x_0=(1,0)$ on the boundary of $\Delta$. Then the velocity of $x_0$
is $\beta (-t)$, and this velocity is transformed into $\lambda \beta(-t)$.
 Now, look at  $A\Delta $. Since $A\Delta $ is an ellipse with curvature
 $-\lambda ^{3}$ at point $Ax_0$, the velocity of $Ax_0$ is $\beta (-t.\lambda ^{3})$.
Using the first identity, we obtain $\beta (-t.\lambda ^{3})=\lambda \beta(-t)$.   
Taking $t=1$, we get $\beta (x)=b.x^{1/3}$ for $x<0$ ($b=\beta (-1)$).
  Now, apply the same technique to $\Delta ^c$ and we get the result
$\beta (x)=a.x^{1/3}$ for $x>0$ ($a=\beta (1)$). 

\skipaline

\noindent (iii) With the same technique as above we obtain that
the function $\beta$ is odd.

\skipaline

\section [The fundamental equation of Image Processing.]{ The fundamental equation of Image Processing.} 

Since the multiscale analysis satisfies the obvious inclusion principle that

 if $A\subset B$ then $T_{t+h,t}(A)\subset T_{t+h,t}(B)$,

 then we can, as well known in the "mathematical morphology school" [Ser], [Mara],
 associate with a picture $u$ the set of its level sets
 $$X_au = \{(x,y), u(x,y) \ge a\}$$  
Then, assuming that each level set is a union of silhouettes, 
we can simply define $T_t(u)$ as

\skipaline

{\noindent \bf [morphological principle]} For any $a$, $t$, $h$ and $u$: $X_aT_{t+h,t}(u) = T_{t+h,t}(X_au)$  

\skipaline

 The corresponding multiscale analysis of images is governed by 
$$ \frac{\partial u}{\partial t} = g(t, curv(u))\vert Du \vert \eqno(3)$$

\skipaline

We say that $T_t$ is governed by equation $(3)$ if for any $u$ $C^2$ and every value $a$ such that
$u(x)=a$ implies $Du(x) \neq 0$ , the equation is true. 
 However, a generalized sense can be given by using the concept of
 "viscosity solution" [AGLM]. Conversely, one can find in [CGG] a proof
 of the existence of viscosity solutions for this equation. We shall
 only prove here that the equation (3) is verified when the image  $u$ 
 is smooth enough. 

\skipaline

Let us prove (3) at any $(x,a)$ such that $u(t,x)=a$ and ($u(t,y)=a$ implies $Du(t,y) \neq 0$).
The last condition implies by the implicit function theorem that $x$ belongs
to a Jordan curve $\Gamma$ enclosing two regions $\Gamma ^+$ and $\Gamma ^-$,
with $u(t,x)<a$ on $\Gamma ^-$ , $u(t,x)>a$ on $\Gamma ^+$ and $u(t,x)=a$ on $\Gamma$.
 Set $u(t)=u(t,.)$. The relation $X_aT_{t+h,t}u(t)=T_{t+h,t}X_au(t)$ implies that $T_{t+h,t}\Gamma ^+$ is
equal to a connected component of $X_au(t+h)$.  Therefore,
the point $x(t+h)$ defined by equation (1) with initial value $x(t)=x$
belongs to the boundary of $X_au(t+h)$. So we obtain $u(t+h,x(t+h))-u(t,x(t))=0$.
Dividing by $h$ and passing to the limit yields 
  $$\frac {\partial u}{\partial t}(t,x) + Du(t,x) \dot x (t)=0 $$
 and using equation (1) and $\vec n(x)=-\frac {Du}{\vert Du\vert}$ we obtain equation (3).   


\skipaline


\section [The "Texton Density" Doctrine of Julesz.]{The "Texton Density" Doctrine of Julesz.}

\rm  
According to Julesz theory [Jul1], texture discrimination is based on what he
calls "local features" (See figure 4 for an example of a pair of discriminable textures
and figure 5 for an example of undiscriminable one). He adds that
 "{\it those local features that might yield texture discrimination should
 be very special ones.  They should be regarded as the} {\bf basic} {\it elements of
 pre-attentive perception, and I  have named such hypothetical elements 
"textons". (...)  It seems that elongated blobs of different width, length,
 and orientation, and perhaps of different first order statistics in small,
 local neighborhoods are the local conspicuous features yielding texture
 discrimination.  (...) Besides colour, there are two additional texton classes:
 elongated blobs (of given orientation, width and aspect ratio) and their
 terminators.   Pre-attentive texture discrimination is based either on the 
difference in the textons or the difference in the first-order statistics 
(or some parameter defined by the first-order statistic, such as density or
 standard deviation) of the textons." (...) One can raise (...) the possibility
 that the pre-attentive textural system (...) can evaluate only 
first-order statistics of textons. (...) Whatever the final number 
of these texton classes will be, it is evident that for texture discrimination,
 the Gestaltist's view has not been corroborated : the global percept of 
texture was found to be decomposable into more basic elements."}

\skipaline

\rm According to Julesz [Jul2], the axioms of the texton theory are as follows :

\skipaline

{\noindent \bf Axiom 1:} {\it  Human vision operates in two distinct modes :}

\noindent Preattentive vision. A system that is parallel
 (independent of number of elements), acting almost instantaneously,
 without scrutiny, and covering a large visual field,
 as in texture discrimination.  Basically a preconscious system
 that knows where texton gradients occur, but is unaware of what
 these textons are.

\noindent {\it Attentive vision. } \rm    Serial search (scrutiny)
 by a small aperture of focal attention in steps lasting 15-50 ms
 each (much faster than eye-movement scanning), as in form
 perception.  Only in this attentional aperture is it consciously 
known what  the textons are.


\skipaline

{\noindent \bf Axiom 2:} {\it Definition of textons} 
{\it (Restricted to line drawings)} \rm

\noindent -Nonoverlapping line segments (black on white background, or white on black
 background, with specific length, orientation, width, velocity, binocular
 disparity, and flicker rate).

\noindent -Terminators (ends-of-lines) of line segments.

\noindent -Crossings of line segments.

\noindent -Blobs, whose shape is unimportant, except for average
length, width, and orientation.

\skipaline


{\noindent \bf Axiom 3:} {\it Texture formation, texton density, texton gradients}

\noindent \rm -The area called the $\Delta$-neighborhood, in which differences in texton 
densities (numbers) are determined and texton-gradients computed,
 is rather limited, and proportional to the size of the texture elements. 
Thus, textures are formed only if the textons are not to sparse, that is, 
if the adjacent textons lie within the $\Delta$-neighborhood.

\noindent -The $\Delta$-neighborhood and the aperture of focal attention are scaled by
 the average extent of the texture elements. So the only global operation
 postulated by the texton theory is the determination of the average element 
size needed to scale the range $\Delta$ of texton interactions.

\skipaline

{\noindent \bf Axiom 4:} {\it The role of textons}

\noindent \rm -Preattentive vision directs attentive vision to the location where 
texton-gradients (i.e. differences in textons, or in the densities
 (number of textons)) occur, but ignores the positional relationships between
 adjacent textons (i.e. the coupling ("glue") between textons is missing).

\skipaline

To summarize, preattentive vision first determines the scale from an aggregate
 of similar elements, i.e. the average element size, and then computes the {\it texton
 gradients} at the boundary of textures, according to the axioms given above. 
 Thus, in preattentive vision, {\it precise positional relationships between
 "textons" are not important; only densities matter.}  The figure 
 proposed by Julesz [Jul1] illustrates this fact by showing two undiscriminable
 textures (fig. 5) wich, for Julesz, have the same density of textons but, however, made of different
 patterns.




\section  [How to define Texton Densities. An Axiomatic Approach.]{ How to define Texton Densities. An Axiomatic Approach.}

\rm The texton doctrine, which is based only on synthetic images,
 neglects to consider an important issue : how can such textons be reliably
 extracted from images of natural scenes ?  Julesz [Jul2] left the question open by accepting a priori any plausible system proposed by biologists or vision researchers : 
"Are line segments just thin, elongated blobs of white and black 
(or vice versa), or do they have the luminance profile of 
the "Mexican-hat-function" or a Gabor-function?  These questions 
can be decided only by doing the psychophysics." 

We can give a rigorous answer to this question by noting that the
texton characteristics indicated by Julesz are shape elements based on curvature and orientation.
Furthermore, these elements are {\it multiscale} because of the a priori unknown
size of the textons. {\it Therefore texton densities are nothing but 
 multiscale curvature and orientation densities.
Now, we have proved in theorem 1 that  there is only one way 
to compute multiscale curvature and orientation}.
 In order to completely formalize the Julesz theory,
 we can consider the following equivalences between formal and
intuitive concepts:

\skipaline

"preattentive" $\Longleftrightarrow$ [pyramidal]

(because no time is given to a feedback in the perceptual system,
which therefore acts as a serie of filters applied successively.)

\skipaline

"line  drawings" $\Longleftrightarrow$ [morphological]

Indeed, the fact that Julesz admits that the performance of human vision
can be characterized by its behavior on line drawings is equivalent to the 
assumption that the structure of a picture is contained in its level sets.
Notice that the Julesz line drawings have some fitness and their boundaries are
"silhouettes" or finite union of silhouettes as discussed above.

\skipaline

"local features" $\Longleftrightarrow$ [Basic principle], [local inclusion of shape]

(because the analysis of shape is local for the filters mentionned above.
Furthermore, the inclusion preservation is due to the fact that the eye
is able to give the right order of sharpness (i.e. curvature) between
shapes observed locally). 

\skipaline

"Black on white or white on black background" $\Longleftrightarrow $ [Reverse contrast inv.]

\skipaline

"only texton densities matter" $\Longleftrightarrow $  local mean values of multiscale
 curvature and orientation are computed.

\skipaline

We add the principle [Affine invariance] because it is well known that the discriminability of plane textures
is little affected by distance and change of position of the plane observer.


Notice that this formalization of Julesz theory simplifies a lot
the kind of texton to be considered: we reduced the blobs, terminators,...
to multiscale curvature and orientation. Now, this reduction is obtained from theorem $1$
since {\it no other local feature can be computed multiscale}. We shall now
see that, in any case, terminators and elongated blobs are
characterized by their multiscale evolution.




\section [Experimental verification of Julesz Theory.]{ Experimental verification of Julesz Theory.}

\rm The preceding equivalences lead to define directly texton densities as
local means of multiscale curvatures and orientations. Thus, we do not need
to really decompose a picture into "blobs" of several sizes and orientations
[MaPe]. However,we almost do it in the following sense: Grayson and 
Gage-Hamilton proved that any silhouette becomes convex before disappearing
when its evolution is governed by equation $(1)$ with $g(t,s)=s$. In the affine 
invariant case $g(t,s)=s^{1/3}$, a similar result has been announced by 
Sapiro and Tannenbaum: any silhouette becomes convex and behaves asymptotically
like an ellipse. Thus the "blobs" characterizing any shape in the theory of 
early vision can be quite well associated with those asymptotic ellipses.
This gives a strong confirmation of intuitions contained in the book of D. Marr [Marr].
According to D. Marr, early vision obeys to what he calls {\it the raw primal sketch}
and this sketch is essentially a decomposition of the image into a family of 
elliptical blobs of several shapes and orientations.

\skipaline 

\noindent {\it Formalization and computation of textons densities}
Let $u_0(x)$ be an image and $u(t,x)$ its multiscale analysis by equation $(3)$.
Then the curvature and orientation at scale $t$ and location $x$ are given
respectively by $curv(u)(x)$ and $\frac{Du}{\vert Du\vert}(x)$ which are both well
defined and computed by equation $(3)$. 

Notice that "blobs" and textons can be white on black or white on black, so we define
for any $\theta \in [0,\pi ]$ and $t>0$ the "density on a ball $B(x,\Delta )$ of textons
at scale $t$ and orientation $\theta $" by:
$$ G_{B_{\Delta }}(x) * (1_{{\Theta }_{\theta ,\delta \theta}} curv^+(u)(t,x))$$
$$ G_{B_{\Delta }}(x) * (1_{{\Theta }_{\theta ,\delta \theta}} curv^-(u)(t,x))$$
where ${\Theta }_{\theta ,\delta \theta }$ is the set of points where 
$\frac{Du}{\vert Du\vert}=(cos\phi , sin\phi)$ verifies $\vert \theta -\phi \vert \le \delta \theta$.
and $G_{B_{\Delta }}(x)$ is the isotropic gaussian with variance $\Delta$.
By $a^+$ we mean $max(a,0)$ and by $a^-$ $max(-a,0)$.   

\skipaline

Then we get a formal definition of texton densities at each scale and orientation.
Based on the obtained texton density channels, a segmentation of the image can be achieved.
If  the Julesz theory is correct, all the pairs of textures which we present as discriminable
should be clearly discriminated by at least one of the texton densities.

Conversely, any pair of  undiscriminable textures should be undiscriminated by all channels.

The basic facts that we discovered by experimentation are following.
 The textures proposed by Julesz, and most textures proposed
 in the litterature as discriminable are easily
discriminated by texton densities even rougher than the announced above:
Indeed, it is enough to compute global curvature densities, that is, we take
$\delta \theta =\pi $ and do not take into account orientation.


\skipaline

Let us now show numerical experiments. First, we analyse basic patterns of Julesz
and present their multiscale analysis obtained with the last equation of theorem 1.
We store the results until scale 9 in figure 1. From this analysis
we extract the multiscale positive curvature (figure 2) and the negative one (figure 3)
at the same scales.

Second, we analyse in the same way two pairs of textures. In figure 4, we store
the 256X256 original image, the analysed image at scale 4, the positive and negative
curvature at scale 4 and the result of a segmentation algorithm applied on the 18 
scale-curvature images (the 9 positive curvatures and the 9 negative). We also show the
negative curvature at scale 1 to emphasize the need of the scale. In figure 5, we
store the original 512X512 image, the corresponding images at scale 7
 and we present the result of the segmentation algorithm. It is very surprising
 because {\it in that case, we achieve hyperdiscrimination}.

 The discrimination is easily achieved and one can even compute the boundary
 by using the segmentation algorithm commented in [KLM].

\skipaline

\noindent N.B. The length unit is the pixel size.
In order to make the scale understable in experiments, we normalized the curvature 
equation in such a way that $T_t$ lets disappear a disk with radius $r$ in time $r$.


\skipaline

\section  [Conclusion.] { Conclusion.}

The axiomatisation of image processing allows an identification of a single
invariant model and subsequent discussion of all psychophysical theories of vision.
Moreover, the verification of these theories can face a priori two types of answers:
a confirmation or a negation. Now, we have seen a third answer: rationalized vision
can be better than the human eye! Psychophysics tends to idealize, as well as
mechanics, the behavior of real beings. So the "formalization" of vision goes beyond
the experimental expectations and opens the possibility of hyperacuity properties.
        
\newpage

\input{renorm.tex}

\newpage


\begin{figure} [htb]
  \insertps{figbio/fig1.PS} {144.8mm}{2mm}
\end{figure}
fig1. Affine Invariant Multiscale Analysis. The original 240x240 image is analysed from scale one untill scale 9.

\newpage


\begin{figure} [htb]
  \insertps{figbio/fig2.PS} {144.8mm}{2mm}
\end{figure}
fig2. Multiscale positive curvature. 

\newpage


\begin{figure} [htb]
  \insertps{figbio/fig3.PS} {144.8mm}{2mm}
\end{figure}
fig3. Multiscale negative curvature.


\newpage


\begin{figure} [htb]
  \insertps{figbio/fig4.PS} {154.4mm}{20mm}
\end{figure}
fig4. Multichannel segmentation using multiscale positive and negative curvatures (18 channels).   



\newpage


\begin{figure} [htb]
  \insertps{figbio/fig5.PS} {154.0mm}{20mm}
\end{figure}
fig5. Multichannel segmentation.

\newpage


\begin{figure} [htb]
  \insertps{figbio/fig6.PS} {154.0mm}{20mm}
\end{figure}
fig6. Multichannel segmentation on four pairs of textures. 


\newpage


\begin{figure} [htb]
  \insertps{figbio/fig7.PS} {154.0mm}{5mm}
\end{figure}
fig7. Multichannel segmentation.


\newpage


\begin{figure} [htb]
  \insertps{figbio/fig8.PS} {154.0mm}{5mm}
\end{figure}
fig8. Multichannel segmentation.


\newpage

{\noindent \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.

\skipaline


[AGLM2] L. Alvarez, F. Guichard, P.L. Lions and J.M. Morel. 
Axiomatisation et nouveaux operateurs 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



 [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


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

\skipaline


[BeJu]  J. Bergen and B. Julesz.      Rapid discrimination of visual patterns.     IEEE Trans. on Systems, Man, and Cybernetics, 13 (5), 1983.

\skipaline


[BPR] J. Beck, K. Prazdny and A. Rosenfeld.     A theory of textural segmentation,     Human and Machine Vision, J.Beck, B. Hope and A. Rosenfeld eds., New York Academic Press, 1983, 1-38.

\skipaline


[Cae]  T. Caelli.     Three processing characteristics of visual texture segmentation.     Spatial Vision, 1(1), 19-30, 1985.

\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


[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



[Enn]  J. Enns. Seeing textons in context. Perception and Psychophysics, 39 (2), 143-147, 1986.

\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, al.
 Invariant descriptors for 3-D object recognition and Pose.
 IEEE Transaction of pattern analysis and machine intelligence.
 Vol 13 N.10 1991.

\skipaline


[FRKV] L. Florack, B. ter Haar Romeny, J.J. Koenderink and M. Viergever.
Scale and the differential structure of images.
Image and vision computing. Vol 10, n. 6 July/August 1992.

\skipaline



[FRKV] L. Florack, B. ter Haar Romeny, J.J. Koenderink and M. Viergever.
General Intensity transformations and Second Order Invariants.
Procedings of the 7th Scandinavian Conference on Image Analysis. Aalborg, august 13-16, 1991.


\skipaline


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

\skipaline


[GBS]  M. Graham, J. Beck and A. Sutter. Two nonlinearities in texture segregation. Proceedings of the ARVO conference, p161, 1989.

\skipaline


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

\skipaline


[JGV]  B. Julesz, E.N. Gilbert and J. D. Victor.     Visual discrimination of textures with identical third order statistics.     Biological Cybernetics, 31, 137-140, 1978.

\skipaline


[JuBe]  B. Julesz and J.R. Bergen.     Textons, the fundamental elements in preattentive vision and perception of textures.     Bell System Tech. J. 62(6) 1619-1645, 1983.

\skipaline


[JuKr]  B. Julesz and B. Kroese.     Features and spatial filters.     Nature, 333, 302-303, May 1988.

\skipaline


[Jul1] B.  Julesz.     Textons, the elements of texture perception, and their interactions.    Nature, 290, 12 March 1981.

\skipaline


[Jul2] B. Julesz.     Texton gradients : the texton theory revisited.     Biol. Cyber. 54, 245-251, 1986.   

\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


[KLM] G. Koepfler, C. Lopez, J.M. Morel. A multiscale algorithm for image segmentation 
by variational method . Accepted at SIAM journal of Numerical Analysis.


\skipaline


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

\skipaline


[KoDo2] J.J. Koenderink and A.J. van Doorn.
Representation of Local Geometry in the Visual System. 
Biol. Cyb. 55 : 367-375, 1987.

\skipaline

  
[Koe1]  J.J. Koenderink. Solid Shape. MIT Press, cambridge, MA 1990.

\skipaline


[Koe2] J.J. Koenderink. The brain a geometry engine. Psychol. Res., Vol 52 (1990)
pp. 122-127.

\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. To appear in J. of Math. Analysis and Applications.

\skipaline


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

\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. Preattentive texture discrimination with early vision mechanisms.     Draft, Department of Electrical Engineering and Computer Science, University of California, Berkeley, CA 94720, June 1989.

\skipaline


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

\skipaline


[Marr1] D. Marr.     Analysing natural images : a computational theory of texture vision.     Cold Spring Harbor Symposium on Quantitative Biology, XL, 647-662, 1976.

\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


[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


[Tre]  A. Treisman.     Preattentive processing in vision.     Comput. Vision, Graphics, Image Process., 31(2), 156-177, 1985.

\skipaline


[VoPo1] H.  Voorhees and T. Poggio.     Detecting textons and texture boundaries in natural images.   Proc. Intern. Conf. Comput. Vision, IEEE, 250-258,  1987.

\skipaline


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

\skipaline


[WeLi]  D. Wermser and C.-E. Liedtke.      Texture analysis using a model of the visual system.
     Proc. 6th Intern. Conf. Pattern Recog., 1078-1080, Munich 1982.

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


