Ce chapitre a \'et\'e \'ecrit en collaboration avec Jean-Michel Morel et a \'et\'e soumis aux C.R. de l'Acad\'emie des Sciences de Paris.

\skipaline

\skipaline

{\small {\noindent \bf Abstract.} Bela Julesz proposed an (informal) axiomatic of the texture preattentive 
discrimination capability of human perception. We translate this axiomatic into 
four formal axioms and prove that the axioms lead to a single multiscale analysis,
governed by a partial differential equation. Therefore, we can numerically
check wether texton theory is true on discriminable and undiscriminable textures.
We obtain a surprising result : texton theory achieves hyperdiscrimination!}

\skipaline

{\small {\noindent \bf R\'esum\'e.} Bela Julesz a propos\'{e} une axiomatique informelle de la discrimination de texture
en vision \pr. Nous traduisons cette axiomatique par quatre axiomes formels
et prouvons que ces axiomes conduisent \`{a} une seule analyse \mul r\'{e}gie
par une E.D.P. Par cons\'{e}quent, nous pouvons valider num\'{e}riquement la \th 
des textons sur des paires de textures discriminables ou indiscriminables en
vision \pr. Nous obtenons un r\'{e}sultat surprenant : la \th des
textons r\'{e}alise l'hyperdiscrimination!} 


\skipaline



\section [Julesz axioms.]{ Les axiomes de Julesz.}

\rm
Selon la \th de Julesz, la discrimination de textures est li\'{e}e \`{a} ce
qu'il appelle "local features". Il ajoute:
 "{\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". }

\skipaline

\rm Les axiomes de la \th des textons sont les suivants :

\skipaline

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

{\noindent \it Preattentive vision.} \rm 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. 

{\noindent \it Attentive vision. } (...)


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



\section [Texton formalization] { Formalisation des textons.}

Les textons sont clairement d\'{e}finis par Julesz comme des formes.
D\'{e}finissons une forme ou une silhouette comme un ensemble ferm\'{e} $X$ dont le
bord est une courbe de Jordan de $\Re ^2$.
La recherche en reconnaissance des formes a d\'{e}fini comme paradigme le concept 
d'{\it analyse \mul}. 
L'analyse \mul vise \`{a} r\'{e}gulariser les formes.    
 Cette r\'{e}gularisation permet d'extraire de mani\`{e}re fiable des caract\'{e}ristiques
locales mais introduit un param\`{e}tre d'\'{e}chelle $t$, qui mesure la perte de localit\'{e}
et le gain en globalit\'{e} de la caract\'{e}ristique extraite (voir [KoDo], [Wit]). 
En r\'{e}alit\'{e}, il est implicite que les concepts d'orientation, de courbure, etc ...
mentionn\'{e}s par Julesz pour caract\'{e}riser les textons sont des concepts multi\'{e}chelle :
On parle de courbure et d'orientation en un point et \`{a} une \'{e}chelle donn\'{e}e.
Nous notons  $T_t(X)$  la {\it forme analys\'{e}e \`{a} l'\'{e}chelle} $t$.
 $X$ est identifi\'{e} \`{a} sa
 fonction indicatrice $X(x)=1$ si $x \in X$ and $0$ ailleurs. 
Nous appelons analyse multi\'{e}chelle une famille d'op\'{e}rateurs $(T_t)_{t \ge 0}$ agissant sur les formes
et nous posons $X(t)=T_t(X)$. 
  
\skipaline

\rm Nous allons d'abord consid\'{e}rer un principe qui s'appelle en \th
de la vision {\it l'architecture pyramidale}. 
D'apr\`{e}s cette hypoth\`{e}se, $T_t$ est d\'{e}duit de $T_s$ pour tous r\'{e}els v\'{e}rifiant $s\le t$ et 
$T_0$ est bien s\^{u}r l'identit\'{e}.
C'est une hypoth\`{e}se n\'{e}cessaire en \th de la vision pr\'{e}attentive 
(irr\'{e}versibilit\'{e} de l'analyse).  
Afin de formaliser l'architecture pyramidale nous introduisons une famille d' {\it op\'{e}rateurs de transition } $T_{t,s}$ 
 index\'{e}s par $0 \le s \le t$  et satisfaisant 

\skipaline

{\noindent \bf [architecture pyramidale]} \rm	    	$T_{t+s} = T_{t+s,s}T_s$ pour tout $0 \le s$, $ 0 \le t$

\skipaline

\noindent Nous posons donc l'\'{e}quivalence informelle/formelle suivante:

Axiom 1 $\Longleftrightarrow$ [Architecture pyramidale]


\skipaline

\rm 
 Supposons que $X$ et $Y$ soient deux silhouettes et que pour tout 
 $x \in \partial Y$ et tout $r>0$,
 on ait $X \cap B(x,2r) \subset Y\cap B(x,2r)$.
Supposons, de plus, que l'inclusion soit stricte i.e., 
 $\partial X$ et $\partial Y$ se rencontrent uniquement en $x$.
 Alors, nous dirons que {\it la forme} $X$ {\it est incluse dans la forme } $Y$ {\it au voisinage de} $x$.
Le principe qui suit exprime que l'ordre entre courbures est pr\'{e}serv\'{e} lors
de l'\'{e}valuation multi\'{e}chelle.

\skipaline

{\noindent\bf [inclusion locale de forme]} \rm Si $X$ est incluse dans $Y$ au voisinage de $x$,
 alors pour $h$ assez petit, $T_{t+h,t}(X) \cap B(x,r) \subset T_{t+h,t}(Y)\cap B(x,r)$.

\skipaline


Le principe qui suit exprime qu'il n'y a pas d'orientation privil\'{e}gi\'{e}e:
un disque reste un disque.

\skipaline

{\noindent\bf [principe de base]} \rm Soit $D=D(x,\kappa)$ un disque de courbure $\kappa$ and de centre $x$.
  Alors $T_{t+h,t}(D)$ est un disque de rayon $\rho (t, h,\kappa ) $ et de centre $x$.
  En outre, la fonction $h \rightarrow \rho(t,h,\kappa) $ est r\'{e}guli\`{e}re.

\skipaline



\noindent En bref, on a l'implication informelle/formelle suivante:

Axiom 2 $\Longrightarrow$ [principe de base], [inclusion locale de forme]


( Car l'analyse de forme est locale et isotrope.
De plus, la conservation de l'inclusion est due au fait que l'oeil est capable
de comparer les angles et les courbures. Ceci est implicite dans
la description informelle des textons: Les "terminators", "crossings" et "blobs" sont des indicateurs
de courbure.)


\skipaline

L'analyse multi\'{e}chelle v\'{e}rifie donc le principe d'inclusion

 si $ A \subset B$ alors $T_{t+h,t}(A) \subset T_{t+h,t}(B)$.

 \noindent On peut alors, comme l'a fait l'\'{e}cole de "morphologie math\'{e}matique"  [Ser],
 associer \`{a} une image $u$ ses ensembles de niveau
 $$X_au = \{(x,y), u(x,y) \ge a\}$$ 

Alors, remarquant que chaque ensemble de niveau est une union de silhouettes, 
nous pouvons facilement associer \`{a} une analyse multi\'{e}chelle
 de forme une analyse multi\'{e}chelle d'image en d\'{e}finissant $T_t(u)$ par

\skipaline

{\noindent \bf [principe morphologique]} Pour tout $a$, $t$, $h$ et $u$: $X_aT_{t+h,t}(u) = T_{t+h,t}(X_au)$  

\skipaline

Quand Julesz se contente de d\'efinir les textons sur des "line drawings", il
admet implicitement le principe morphologique.

\noindent "line drawings" (Axiom 2) $\Longrightarrow$ [morphologique]



\skipaline

Le principe suivant de l'analyse de forme est l'invariance affine.
Posons $AX(x) = X(Ax)$ pour toute transformation lin\'eaire $A$.
Nous ajoutons le principe [invariance affine] car la discriminabilit\'{e} de textures planes
est peu affect\'{e}e par la distance et le changement de position de l'observateur.

  

\skipaline

{\noindent \bf [invariance affine]}. {\rm	Pour tout $A$ et $t \ge 0$, il existe une fonction $t'(t,A) \ge 0$ de classe $C^1$ telle que
 $AT_{t'(t,A),t'(s,A)}=T_{t,s}A$.}

\noindent \rm Il a \'{e}t\'{e} prouv\'{e} dans [AGLM] que l'on peut toujours supposer $t'(t,A)=t.\vert detA\vert^{1/2}$.  
 Cette relation signifie que le r\'{e}sultat de l'analyse multi\'{e}chelle $T_t$ est
 ind\'{e}pendant de la taille et de la position dans l'espace de la forme  analys\'{e}e.
 Une transformation lin\'{e}aire correspond \`{a} une anamorphose d'une image plane lorsqu'elle est pr\'{e}sent\'{e}e \`{a}
 l'oeil \`{a} une distance arbitraire avec une orientation quelconque dans l'espace.
 Finalement notons que
le texton peut \^{e}tre noir sur blanc ou blanc sur noir, et c'est \'{e}quivalent :

\skipaline

{\noindent \bf [invariance par inversion du contraste]}  $T_{t+h,t}(X^c)=T_{t+h,t}(X)^c$

\skipaline

"Black on white or white on black background (Axiom 2)" $\Longrightarrow $ [invariance par inversion du contraste]


\section [The fundamental equations of shape and image analysis.]{ Les \'{e}quations fondamentales de l'analyse de formes et d'images.}

 \rm
 Lorsqu'un point $x$ appartient \`{a} une courbe plane de classe $C^2$ qui \'{e}volue, nous allons noter
 $\dot {x}$ la d\'eriv\'{e}e temporelle de $x$,
 qui est un vecteur de $\Re ^2$. On note $curv(x)$ la courbure
 de la courbe en $x$.

\skipaline 

{\noindent \bf Th\'eor\`eme 1.} {\it (i) Sous les cinq principes (pyramidal, inclusion locale de forme,
 principe de base, invariance affine, invariance par inversion du contraste), 
l'analyse multi\'echelle de forme est r\'{e}gie par l'\'{e}quation
$$ \dot{x} =  (t.curv(x))^{1/3} \vec n(x) \eqno(1)$$


\noindent (ii) Si nous ajoutons le principe morphologique,
 l'analyse d'images associ\'{e}e est r\'{e}gie par l'\'equation 
$$ \frac{\partial u}{\partial t} = (t.curv(u))^{1/3}.\vert \nabla u \vert \eqno(2)$$

 }
  
\skipaline


L'\'{e}quation (2) a \'{e}t\'{e} introduite et justifi\'{e}e axiomatiquement 
 (d'une fa\c {c}on plus compliqu\'{e}e cependant) dans [AGLM].
L' \'{e}quation (1) a \'{e}t\'{e} propos\'{e}e et \'{e}tudi\'{e}e dans [SaTa]. En fait,
avec cette axiomatique, la d\'{e}monstration est
\'{e}l\'{e}mentaire:  



\skipaline
  
\noindent (i) Soit $X$ une silhouette. Supposons que $T_t(X)$ ait un bord  $C^2$
 qui soit une vari\'{e}t\'{e} de classe $C^2$ au voisinage d'un point $x$ de $\partial T_t(X)$.
 Alors elle admet une courbure $\kappa$ au point $x$ et nous pouvons consid\'erer un disque sousosculateur et
 surosculateur, i.e., un disque $D$ de courbure $\kappa -\epsilon $ et un disque
 $D'$ de courbure $\kappa+\epsilon $, tangents \`a la silhouette en $x$.
 En \'{e}crivant le principe pyramidal et d'inclusion locale des formes, nous voyons que   
$$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) $$
  Donc, en notant $x(t+h)$ le point de $\partial T_{t+h}(X)$
 tel que $x(t+h) -x(t)$ soit parall\`{e}le \`{a} $\vec n(x)$, nous obtenons
$$\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 )$$
  En divisant par $h$ et en passant \`a la limite lorsque $h$ tend vers $0$ 
  et ensuite en faisant tendre $\epsilon$ vers $0$, nous obtenons gr\^ace au principe de base l' \'equation 
$$ \dot x=\frac{\partial \rho}{\partial h}(t,0,\kappa)\vec n$$
Des calculs alg\'{e}briques assez simples exploitant l'invariance affine puis l'invariance par inversion du contraste
conduisent \`{a} l'\'{e}quation (1) (voir [AGLM]).
Ensuite, Il suffit de d\'{e}river une fois la relation $u(t,x(t))=\lambda$ par rapport \`{a} l'\'{e}chelle $t$ pour obtenir (2).



\section [Experimental confirmation of Julesz Theory.]{ V\'{e}rification exp\'{e}rimentale de la \th de Julesz.}


\noindent Les \'{e}quivalences pr\'{e}c\'{e}dentes et l'axiome 3 permettent de d\'{e}finir les densit\'{e}s de textons 
\`{a} partir de la courbure et de l'orientation \mul .
 Soit $u_0(x)$  une image et $u(t,x)$ son analyse obtenue avec l'\'{e}quation $(2)$.
Alors la courbure et l'orientation \`{a} l'\'{e}chelle $t$ et la position $x$ sont donn\'{e}es
respectivement par $curv(u)(x)$ et $\frac{Du}{\vert Du\vert}(x)$ qui sont bien
d\'{e}finies et calcul\'{e}es par l'\'{e}quation $(2)$.
 {\it Si la \th de Julesz est correcte, n'importe quelle paire de textures indiscriminables
devrait avoir des courbures multi\'{e}chelles indiscriminables.}
L'exp\'{e}rimentation num\'erique nous a permis de constater les faits suivants.
Les textures propos\'{e}es par Julesz et celles propos\'{e}es
dans les publications comme discriminables pr\'{e}attentivement sont facilement discriminables
en utilisant les densit\'{e}s de textons. 
Voyons maintenant une paire indiscriminable classique due \`{a} Julesz. Dans la figure 1, apparaissent
l'image originale (512x512), l'image analys\'{e}e \`{a} une certaine \'{e}chelle ($t=7$ pixels),
 les courbures
n\'{e}gatives et positives de l'image analys\'{e}e et le r\'{e}sultat
 d'une segmentation
\mul lorsqu'on d\'{e}cide de garder deux r\'{e}gions.
 Dans ce cas (et dans toutes les textures indiscriminables propos\'{e}es
 dans la litt\'{e}rature), nous r\'{e}alisons une {\it hyperdiscrimination}!
( Le dernier quadrant illustre la n\'{e}cessit\'{e} d'extraire une courbure \`{a} plusieurs
 \'{e}chelles pour l'hyperdiscrimination car la courbure n\'{e}gative de l'image originale
ne permet pas de conclure.)

\skipaline

La \th est-elle donc "trop bonne" pour rendre compte de la vision humaine? Nous
pensons qu'il faut pr\'{e}ciser l'axiome 3 en disant que la perception \'{e}value
l'\'{e}chelle significative des textons, proportionnelle au "$\Delta$-voisinage".

\noindent 1) Si les textons sont trop isol\'{e}s, ils sont discrimin\'{e}s comme des formes
car personne ne doute qu'un "5" et un "10" ne soient deux formes distinctes!

\noindent 2) Si les textons sont suffisamment rapproch\'{e}s, alors on doit supposer
que l'analyse multi\'{e}chelle va \^{e}tre inhib\'{e}e [MaPe] d\`{e}s qu'on d\'{e}passe une
\'{e}chelle petite devant le "$\Delta$-voisinage". Si on l\`{e}ve cette inhibition,
ce qui ne pose aucun probl\`{e}me num\'{e}rique, on obtient l'hyperdiscrimination.    

\skipaline

{\noindent \bf References.}

\skipaline 

[AGLM] L. Alvarez, F. Guichard, P.L. Lions and J.M. Morel. Axiomes et \'{e}quations fondamentales
du traitement d'images. Rapport 9216, CEREMADE. Universit\'e Paris Dauphine, 1992.

\skipaline 


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

\skipaline 


[KoDo] J.J. Koenderink and A.J. van Doorn. Dynamic shape. Biol. Cyber. 53, 383-396, 1986.
 
\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 


[MaPe]  J. Malik and P. Perona. Preattentive texture discrimination
 with early vision mechanisms. J. Optical Society of America, May 1990, pp. 923-932.
 
\skipaline 


[SaTa] 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 

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

\skipaline 


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

\newpage

\input{lopez/plancras.tex}
