This chapter has been written in collaboration with Jean-Michel Morel and the experiences have been done with Christian Lopez. 

\section[Introduction]{Introduction.}

What is ``texture'' ?  An answer could be to simply show a serie of examples
of what is meant by texture :  a series of this kind can be found in the
Brodatz book \cite{Bro} from which we extract the figure~\ref{fig_Tex1.2} .  This answer is of course not satisfying.  Indeed, it is as difficult to give a list of all textures as to describe the whole world.  Moreover, even if such a list of all textures was available, there would be no certainty that new kinds of
textures will not arise.  Think that new patterns are created every day by
artists and designers.  Who had any idea for instance of the textures of
scotch kilts before they were found ?  

%-----fig_Tex1.2-----
\begin{figure}[htb]
  \insertps{figures/Tex1.2.PS}{60mm}{29mm}
  \caption{Brodatz textures (from left to right) : Brick wall, Straw, plastic bubbles, pressed calf leather, bark and heringbone wave.}
  \label{fig_Tex1.2}
\end{figure}
%------------------

Another method could be to give some generic description of textures, like
{\em ``a texture is an almost periodic structure''}.   But for any such definition, you can be sure that some counterexample which still is acknowledged as
``texture'' will be found and contradict this definition.  For instance, the
picture of a cloud will surely contradict the naive definition we gave
above.  The Gestaltists tend to assimilate the textures to the result of a
``grouping'' process, by which similar patterns in a picture tend to form a
``perceptual set'', a "Gestalt".  

%-----fig_Tex3-----
\begin{figure}[hb]
  \sinsertps{figures}{200mm}{75mm}
  \caption{Examples of preattentively distinguishable (above) and undistinguishable (below) textures (from [Vis]) .}
  \label{fig_Tex3}
\end{figure}
%------------------

Psychophysicists and vision researchers have proposed an alternative
approach : the texture discrimination theory.  They do not try to define a
texture, but rather to decide when a given perceptual system can
discriminate two textures.  Look at the examples of figure~\ref{fig_Tex3} : above, one sees two sets of bars which can be immediately discriminated, probably
because of the difference of orientation.  Below, it is difficult to say
anything at first glance, and only a scrutiny will show that the picture is
divided  into two regions made of triangles with opposite orientation.  
Therefore there is no intrinsic texture recognition, by which a human could
look at a texture, make a complete model of it, and thereafter be able to
reconstruct it.  Some information is lost, and the texture discrimination
seems to be based on some texture measures, whose variations would be
the basis of discrimination.  The incompleteness of these measures could
be an explanation for the undiscriminability of certain texture pairs.   


 Following R. Vistnes~\cite{Vis}, we note that a texture measure can
generally be classified as ``statistical'' when it measures statistics of
pixels (such as gray-level mean or variance), or ``structural'' when it
measures features (such as length or orientation) of image structures and
their spatial relations~\cite{Har1}.  It has been argued elsewhere that
methods relying only on pixel statistics are conceptually flawed, since the
processes from which image textures arise create related structures in
the scene, which project to related regions in the image, rather than
related pixels (\cite{Mue}, \cite{AhS}).  Researchers have
investigated a variety of ``structural'' texture measures, including contrast
or edge density~\cite{Har1}; spatial relations of edges or other image
structures, captured in generalized co-occurrence matrices~\cite{DavCA}; properties such as length, orientation  and density of texture elements~\cite{TsT,VoP1,Marr2,MaleBF}; and inferred surface roughness via estimated fractal dimension~\cite{Pen1,PelNHA}.  Many structural methods attempt to isolate texture elements and calculate their attributes and spatial relations ~\cite{TomST,ConnH,MatSN,LeuW,VilNP}.  

Similarly, one may view the equally large body of research on human
texture discrimination (as exemplified by that of~\cite{Bec2,Ju2,Ju3,Tr} and their colleagues) as an attempt to identify the set of
texton measures employed by the human visual system.  Although it is
hopeless, as we stated above, to try to model the vast class of natural
texture-generation processes, it is straightforward to construct machines
that mimic human texture perception, simply by measuring the same image
features as  humans do.  Several researchers have attempted to do this,
using various models of human texture perception~\cite{Cae,BergenJ1,Rea,TamMY,Tr,VoP1,WermL,MaliP2}. 
\clearpage

Recent litterature shows a spectacular convergence of the different
schools towards a unified theory, which will be explained in the next
section under the name of "textons doctrine".   As noticed by H.  Voorhees
and T. Poggio~\cite{VoP1}, one of the first complete expositions of this doctrine has been made by David Marr~\cite{Marr2} who proposed that texture is represented in the raw primal sketch : a symbolic description of localized intensity
changes in the image, including edges, compact blobs, and linear blobs
called bars.   This theory assumes that in the human visual system,
attributes of these tokens -- their size, orientation, contrast, and
termination points -- are computed, along with their position.  Texture
boundary detection and the extraction of form proceeds by comparing first
order statistics of distributions of these attributes -- size, orientation,
contrast, and density -- over nearby neighbourhoods.  It should be noted that
various neurophysiologically identified analysers tuned to blobs of convex
shapes had been found in visual cortex of vertebrates (e.g. Hubel and Wiesel,
1962~\cite{HubW}).

%-----fig_Tex4-----
\begin{figure}[htb]
  \sinsertps{figures}{140mm}{75mm}
  \caption{Iso-second-order texture pair above threshold of preattentive texture discrimination (from [JU2]) .}
  \label{fig_Tex4}
\end{figure}
%------------------

Since the primal sketch theory was proposed, a number of psychophysicists
have studied human texture perception.  Julesz (who had previously held
the opposite view) demonstrated that first order local statistics of blobs
better account for perceived texture differences than second order global
statistics of pixels.  He concluded that blobs called ``textons'' -- together with their geometric and intensity attributes, termination
points, and crossings -- form the primitives on which texture perception is
based.   Indeed, the original Julesz conjecture said that ``iso-second-order
textures are indistinguishable''.  It has been disproved.  In figure~\ref{fig_Tex4} one can see a very simple counterexample : the building blocks of this example are two micropatterns having exactly the same second order statistics.  They
are used for generating two discriminable textures, which inherit this
identity of second order statistics.  Intuitively, the discrimination is due
to the formation of local curve-like features in one of the textures.   A
plausible explanation is that the visual system is especially sensitive to
this kind of features, the so called ``textons''.

Many psychophysical studies of texture perception have thereafter
assumed the existence of texton detectors, employing synthetic images of
symbols such as line segments.  One of the last significant adhesions to
this doctrine is that of Gestaltists like Beck who gave up the ``grouping'' dogma which was first introduced by Wertheimer~\cite{Wert}, let us quote \cite{BecSI} :
\begin{quote}
\em (...) segregation is primarily a function of spatial frequency components 
and not of perceptual grouping processes.  Perceptual grouping processes
may also affect texture segregation.  Such processes aggregate elements
on the basis of proximity and similarity and segregate regions in terms of
emergent properties such as length.  Geometric attributes and spatial
relations such as the elongatedness of texture elements, contour
smoothness, and contour alignment have been found to affect texture
segregation.  The effects of these variables cannot be explained in terms
of low spatial frequency differences.
\end{quote}
\clearpage

As we shall see, this convergence of psychophysicists, Gestaltists,
biologists and vision researchers has gone as far as to agree on the first
stage of the texture measure computation : it should be a multiscale linear
filtering, based on a convolution of the analysed picture with a Gabor-like
function with few oscillations.  In other terms, an  oversampled Wavelet
analysis~\cite{Mall},\cite{Me}.  In the next section, we shall develop the ``texton'' doctrine; in section~\ref{sec_TeEx} we present and discuss three exemplary
computational approaches to texton theory : the Voorhees and Poggio
approach, based on David Marr, the Bovik, Clark and Geisler algorithm, and
finally one of the most recent and complete, Malik and Perona's
discrimination algorithm.  In section~\ref{sec_tex_examples}, we propose a synthesis of these
approaches and design a universal discrimination algorithm using our general segmentation algorithm.

\section[L'hypoth\'etique doctrine des ``textons'']{The hypothetic ``textons'' doctrine.}

Let us quote how Julesz introduces his texton theory~\cite{Ju2} :
\begin{quotation}
\em The existence of many indistinguishable iso-second-order textures has
established that the pre-attentive visual system is unable to process
statistical information beyond the second order.  The next question is
whether iso-second-order texture pairs do exist that yield pre-attentive
texture discrimination.  If they do, such texture discrimination must be the
result of local features.  As we have seen that many seemingly conspicuous
features do not yield texture discrimination in iso-second-order
statistical constraint, those local features that might yield texture
discrimination should be very special ones.  They should be regarded as the
basic 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 neighbourhoods are the local conspicuous features yielding texture discrimination.  (...) Besides color, 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
globally cannot even compute second-order statistical parameters, but 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.
\end{quotation}
\mbox{}
\medskip
\newline
According to Julesz~\cite{Ju3}, the axioms of the texton theory are
as follows :
\begin{description}
\item[Axiom 1 :] Human vision operates in two distinct modes.
\begin{description}
\item[-] {\em 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.
\item[-] {\em Attentive vision.}  Serial search (scrutiny) by a small aperture of focal attention in steps lasting 15-50 $\mu$s each (much faster than eye-movement
scanning), as in form perception.  Only in this attentional aperture it is
consciously known what  the textons are.
\end{description}
\item[Axiom 2 :]  Definition of textons. (Restricted to line drawings)
\begin{description}
\item[-] Nonoverlapping line segments (black on white background, or white on
black background, with specific length, orientation, width, velocity,
binocular disparity, and flicker rate).
\item[-] Terminators (ends-of-lines) of line segments.
\item[-] Crossings of line segments.
\item[-] Blobs, whose shape is unimportant, expect for average length, width, and orientation.
\end{description}
The figure~\ref{fig_Tex5}, extracted from Malik and Perona \cite{MaliP2}, illustrates the different kinds of  textons and their discriminatory power.
\item[Axiom 3 :] Texture formation, texton density, texton gradients.
\begin{description}
\item[-] The area called the $\Delta$-neighbourhood, 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$-neighbourhood.
\item[-] The $\Delta$-neighbourhood 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.
\end{description}
\item[Axiom 4 :] The role of textons.\\
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).
\end{description}

%-----fig_Tex5-----
\begin{figure}[htb]
  \sinsertps{figures}{150mm}{75mm}
  \caption{Examples of textures (from [MaliP2]) .}
  \label{fig_Tex5}
\end{figure}
%------------------
\clearpage

To summarize, preattentive vision first determines the scale from an
aggregate of similar element, i.e. the average element size, and then
computes the texton gradients at the boundary of textures, according to
the axioms given above.{\em Thus, in preattentive vision, precise positional
relationships between ``textons'' are not important; only densities matter.} 
The figure~\ref{fig_Tex6} proposed by Julesz~\cite{Ju2} illustrates this fact by showing two undiscriminable textures with the same density of textons but, however, made of different patterns.

%-----fig_Tex6-----
\begin{figure}[hb]
  \insertps{figures/Tex6.PS}{120mm}{20mm}
  \caption{Two undiscriminable textures : $\sqcup\!\sqcap$ and $\overline{\sqsubset\!\!\!\sqsupset}$ having the same number of terminators and of long -- resp. short -- bars , (from [Ju2]) .}
  \label{fig_Tex6}
\end{figure}
%------------------

\section[Comment d\'efinir les textons et comment les calculer : quelques th\'eories]{How to define textons and how to compute them : some theories.}
\label{sec_TeEx}

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 ~\cite{Ju3} left the question open
by accepting a priori any plausible system proposed by biologists or vision
researchers : 
\begin{quote}
\em 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.
\end{quote}
Let us begin with the approach proposed by the school of David Marr.

\subsection[L'algorithme de Voorhees et Poggio]{The Voorhees and Poggio algorithm.}

The algorithm of these authors~\cite{VoP2} has five stages : Rough blob or bar 
detection, compact blobs segmentation, bar segmentation, attribute
computation and removal of spurious blobs, texture boundary detection.
\begin{enumerate}
\item For \underline{rough blob or bar detection} they use the sign bits of $I\star \Delta G$ (see figure~\ref{fig_Tex7}). In this sense, blobs may be regarded as duals of edges, which can be detected using the zero crossings of $I\star \Delta G$.  Instead of thresholding at zero, however, a small threshold is used which removes some connections between blobs due to noise. A difficulty of this approach is that one cannot simply treat connected components of the thresholded $I\star \Delta G$ array as textons, since these regions can span large distances in the image.  In order to compute meaningful attributes of blobs, such regions must be
segmented into localized blobs and bars.  Thin joins between otherwise compact bars must be eliminated.  Also, elongated regions must be separated at bends and intersections into roughly linear bars. 
\item \underline{Compact blob segmentation} : Often, for a particular level, two nearby extrema of $I\star \Delta G$ may be joined into a single blob, containing a thin neck. These connections are sensitive to the level chosen and may result in connected regions which span large portions of the image. Such regions
are segmented using multiple levels. Whenever a higher level would result
in a region being split into two or more regions, the new regions are used
provided that they are relatively stable.  The stability criterion  ( similar
to the stability criterion for fingerprints proposed by Witkin~\cite{Wi2} ) requires that the new regions exist over at least as large a range of levels
than the underlying one.  The splitting operation is applied recursively at
several levels.  Finally, the new, smaller regions are numbered and then
grown back over the original regions in order to segment them. 
\item \underline{Bar segmentation.} Elongated regions can be segmented at junctions and bends by using a refinement of the medial axis transform. 
The medial axis, obtained by thinning the region down to its skeleton, has
been criticized for being sensitive to slight perturbations in the region
contour.  However, a stable representation can be obtained by keeping only
those segments of the skeleton which represent elongated sections of the
region. The algorithm removes insignificant skeleton segments, retaining
only those which represent elongated, bar-like parts of the region.  The
remaining segments, numbered, are then grown back over the original
region, segmenting it into approximately linear segments.  Compact
regions, which have no significant skeleton segments, are not segmented. 
\item \underline{Attribute computation.}  At this point the blob regions have been segmented into localized blobs, whose attributes can be computed.  The
length, width, and orientation of each blob is computed from its second
moments.  
\item \underline{Texture boundary detection.}  By a texton $i$, the authors mean a blob, or a bar with its attributes fixed in a certain range $I_i$.  (For instance, for the bars, one can divide the interval of possible directions into six subintervals, this yields six ``textons'').  Following the texton doctrine, texture boundaries can be roughly located by computing the statistic between adjacent neighbourhoods $O_1$ and $O_2$ over the entire texton image. Let $f_{1i}$ and $f_{2i}$  be  the frequencies of texton $i$ in both neighbourhoods.  The texton gradient between both neighbourhoods,  is then $\Disp{\max_i} |f_{1i}-f_{2i}|$.  The width of each $I_i$ equals approximately the minimum preattentively perceivable difference of the attribute.
\end{enumerate}

%-----fig_Tex7-----
\begin{figure}[hb]
  \sinsertps{figures}{180mm}{75mm}
  \caption{a. Image of a leopard; b. The computed textons (blobs and bars) ; \hspace{1.5cm} c. Texture boundaries due to density as found by Voorhees and Poggio's algorithm (from [VoP2]) .}
  \label{fig_Tex7}
\end{figure}
%------------------


\subsection[Un mod\`ele de discrimination par fr\'equences spatiales]{A spatial frequency discrimination model. \newline (A.C. Bovik, M. Clark and W. S. Geisler)}

These authors propose \cite{BovCG} a spatial filtering approach for texture analysis. Specifically, texture images are encoded into multiple narrowband channels.  The output of each channel is a 2-D complex-modulated signal
whose amplitude and phase envelopes are used to segregate regions based
on spatial frequency and orientation.  Thus, texture is interpreted as a
``carrier'' of region/surface information.  The channel filters used, known
as 2-D Gabor filters, can be defined to cover any elliptical portion
of frequency space, and have optimal joint resolution in space and spatial
frequency.  This approach was first justified by Daugman~\cite{Daug1,Daug3}, Pollen and Ronner~\cite{PolR}, Webster and De Valois~\cite{WebDV}.  According to Marcelja\cite{Marc}, the Gabor filters closely approximate cortical receptive fields whose purpose remains uncertain.

\clearpage 

\subsubsection*{Description of the algorithm.}

Let $(x, y)$ be any Euclidian coordinate system.  Define a Gabor function as
$$h_n(x, y) = G(x, y)\exp(2\pi inx),$$
where 
$$G(x, y) = \frac{1}{2\pi\sigma^2}\,\exp\left[-\frac{\left(\Dfrac{x}{\lambda}\right)^2+y^2}{2\sigma^2}\right].$$
Thus, $h_n$ is a complex sine with frequency $n$ in the direction $x$ and $0$ in the $y$-direction, modulated by a Gaussian with aspect ratio $\lambda$, scale parameter $\sigma$, and major axis oriented as the $x$-axis. Its frequency response (or in other terms its Fourier transform) is
$$H_n(u,v) = \exp(-2\pi^2\sigma^2(u-n)^2\lambda^2 + v^2).$$
Assume that the picture $g(x,y)$ behaves near $(0,0)$ as $g(x, y) = \Re\Disp{\left(e^{2i\pi px}\right)}$.  Then it is easy to see that the filtered picture $g\star h_n$ will have a ``maximum response'' near $(0,0)$ for $p=n$. Indeed, 
$$|g\star h_p(0,0)| = \left|\int G(x, y)e^{-2i\pi(n-p)}d\!x\!d\!y\right|,$$
 which is exponentially decreasing as $n-p$ tends to infinity. A first version of the texture discrimination algorithm uses this remark by taking a set of Gabor filters with different orientations, sizes and frequencies, $h_1$, \ldots, $h_k$, and by associating to each point $(x, y)$ of the picture a label $i$ belonging to $\{1, \ldots, k\}$. The label is given by $i(x, y) = \arg\max (|h_k\star g(x, y)|)$.  Then the texture segmentation problem is led back to a classical boundary detection problem.   

An important improvement is obtained if the moduli of the spatial
frequency responses are smoothed by a Gaussian filter with the same
shape as G, but with a bigger size.  (A good ratio is, according to these
authors, 3/2).

However, the authors notice that the moduli of the response are not always
enough to discriminate two textures.  They take the following example : an
image whose upper part is made of vertical regularly spaced bars, and
whose lower part is made of the same bars, slighthly shifted.  Of course,
both patterns have exactly the same moduli of spatial frequency responses.
However,  an ``illusory line'' arises on the boundary of both patterns because
they have a difference in phase.  Therefore, these authors propose to
discriminate such textures by a labeling algorithm of the preceding type,
but based on the phase (more precisely on the Laplacian of phase) instead
of the modulus of the frequency response.

\subsection[Le mod\`ele ``computationel'' de Malik et Perona]{The  Malik and Perona computational model.}

Their model(see~\cite{MaliP2}) is motivated by detailed comparison with psychophysics and physiology and makes predictions about the degree of discriminability of different texture pairs which seem to match very well with experimental
measurements of discriminability in human observers due to Kr\"{o}se~\cite{Kr} and Gurnsey and Browse~\cite{GurB}.
\smallskip
\newline
The model consists of three stages : 
\begin{enumerate}
\item The image $I(x,y)$ is convolved with a bank of even-symmetric linear
filters $F_k$ followed by half wave rectification (we will indicate the
positive part with $R^+ (x,y) = \max( R(x, y),0)$ and the negative part with
$R^-(x, y) = \max( -R(x,y),0)$ giving a set of ``neural'' responses $R_i(x, y)$ whose index $i$ identifies the orientation-frequency ``channel'' :
$$R_{2k} = (I\star F_k)^+ \,\mbox{ and }\,   R_{2k+1} = (I\star F_k)^-.$$
There are two kinds of filters $F_k$ :  radially symmetric filters $F_k$ which
model non-oriented simple cells and are simply combinations of circular
gaussians of varying size,  and directionally tuned filters with an
even-symmetric cross section perpendicular to the axis which model
bar-sensitive simple cells.   All these functions have zero mean value and
must be therefore considered as smooth derivatives.  (see figure~\ref{fig_Tex10}).\\
More precisely, set 
$$G(x_0, y_0,\sigma_x,\sigma_y) =\frac{1}{2\pi \sigma_x\sigma_y}\,\exp\left[-\left( \frac{(x-x_0)^2}{\sigma_x^2} + \frac{(y-y_0)^2}{\sigma_y^2}\right)\right].$$
Then three types of linear combinations are considered
\begin{description}
\item[a)] Linear combinations of two circular concentric gaussian functions
$$DOG1(\sigma) = G(0,0,0.71\sigma,0.71\sigma)- G(0,0,1.14\sigma,1.14\sigma).$$ 
\item[b)] Linear combinations of three circular concentric gaussian functions
$$DOG2(\sigma) = G(0,0,0.62\sigma,0.62\sigma)-2\cdot G(0,0,\sigma,\sigma) + G(0,0,1.6\sigma, 1.6\sigma).$$
\item[c)] Linear combinations of three offset identical anisotropic gaussian
functions
$$DOOG2(\sigma) = G(0,\sigma,3\sigma,\sigma)-2\cdot G(0,0,3\sigma,\sigma) + G(0,-\sigma,3\sigma,\sigma).$$
The other DOOG2 filters are obtained by 6 rotations about the center of the middle gaussian.
\end{description}
\item The second stage of the model is nonlinear inhibition, localized in
space, within and among the neural response profiles which results in the
suppression of weak responses when there are strong responses at the
same or nearby location.\\
Thresholds \mbox{\hspace{1.5cm}} $T_i(x_0,y_0) = \Disp{\max_j\max_{(x,y)\in I_{ji}(x_0,y_0)}} a_{ji}R_j(x,y)$, 
\smallskip
\newline
where $I_{ji}$ is the neighbourhood of $(x_0,y_0)$ in which neurons in channel $j$ are able to inhibit neurons in channel $i$, $a_{ij}$ is a measure of the effectiveness of this inhibition. The ``post-inhibition response'' is given by
$$PIR_i(x_0,y_0) = \max_{(x,y)\in S_i(x_0,y_0)}  \frac{1}{1- a_{ii}}(R_i(x,y) - T_i(x,y))^+,$$
where $S_i(x_0,y_0)$ is a sampling neighbourhood from which the strong
responses in channel $i$ are selected for subsequent processing. The size of
the neighbourhoods $I_{ij}$ varies between $1.25\sigma$ and $2\sigma$, where $\sigma$ is the variance of the involved filters.
\item Texture boundary detection using peaks in the gradients of the inhibited
response profiles. The texture gradient at $(x,y)$ is defined as $\Disp{\max_i}(PIR_i\star G_{\sigma'})(x,y)$.\\
As the authors say : {\em The maximum operation seems a natural way of combining the outputs of different channels. The size of the gaussian $G_{\sigma'}$ is chosen heuristically.}
\end{enumerate}

%-----fig_Tex10-----
\begin{figure}[hb]
  \sinsertps{figures}{100mm}{75mm}
  \caption{Filters used by Malik and Perona, for the definitions of a, b and c see the text (from [MaliP2]) .}
  \label{fig_Tex10}
\end{figure}
%------------------

\subsubsection*{A weakness of the ``nonlinear inhibition'' mechanism.}

\label{TextA_Ad}The basic idea of the nonlinear inhibition of Malik and Perona is that if at some point $(x,y)$ a response $R_i$ is greater than $a_{ji}R_j$ for some $j$, then it will ``inhibit'' the response $R_j$.  Now, the smallest $a_{ji}$ is of the order of 0.15.  Let us consider the following  example. Assume that the texture $\cal A$ is made of a grid of micropatterns equal to $F_i$ and that the texture $\cal B$ is obtained by adding to $\cal A$ a tenth of a texture $\cal C$ made of the same grid, with micropatterns $F_j$.  Assume further that the filters $F_i$ and $F_j$ are almost orthogonal, which is achieved, for instance, by two identical $DOOG2$ functions, but with perpendicular axis. Roughly speaking, $\cal A$ will appear to be made, say, of vertical bars, while $\cal B$  will have the same vertical bars plus some weak horizontal bars.  There is no doubt about the discriminability, even if the coefficient of $F_j$ in $\cal C$ is much smaller than 1/10 (see also figure~\ref{fig_Seg_TextA_Ad}) .

Then it is rather natural to think that the filter which will contribute
most to the discrimination is $F_j$, and that the filter which contributes the
less is $F_i$.  However, that is not the case, for the large response $R_i$ inhibits everywhere the small response $R_j$. Indeed, $F_j\star {\cal B} = F_j\star{\cal A} + (1/10) F_j\star{\cal C} \simeq (1/10) F_j\star{\cal C}$, while $F_i\star{\cal B} \simeq F_i\star{\cal A}$. Thus, in this kind of case, which occurs frequently, the nonlinear inhibition will be a drawback to discrimination.


\subsection[Synth\`ese]{Synthesis.}

The three computational theories resumed above present four stages of
processing , which can be more or less sophisticated but are always
isolable.

\subsubsection*{Stage 1: Multiscale Wavelet filtering.}

The Wavelet of Voorhees and Poggio is the classical one, coming from
David Marr's primal sketch : the Laplacian of Gaussian $\Delta G$.  Malik and Perona use several wavelets : two of them are isotropic and the third is elongated, and taken in six directions. They have the visual aspect of a black bar
between two white bars.  Bovik, Clark and Geisler use an elongated
Gaussian (``black blob'') in four directions and four elongated Gabor
functions with two oscillations, having all the aspect of five alternate
white and black bars.  In this last case, the multiscale aspect of the
algorithm is implicit, since the scale of the functions is adapted a priori
to the scale of the analysed textures.  Following Malik and Perona's
notation, we call $F_i$ the channels (``responses'') obtained by this linear
filtering.

\subsubsection*{Stage 2: Half- or full-wave rectification.}

It is the first nonlinear processing, which will be  discussed in next section with more details. The $R_i$ are transformed into $R_{2i} = \max (F_i,0)$ and $R_{2i+1}= \max (-F_i,0)$. This operation is called by Malik and Perona ``half-wave rectification''.  Voorhees and Poggio, for better elimination of noise effect, use the variant $R_i^+ = \max (R_i,\epsilon)$ where $\epsilon$ is an ad hoc  small constant. Bovik, Clark and Geisler use ``full wave rectification'', that is $R_i = |F_i|$.

\subsubsection*{Stage 3: Collateral inhibition.}
 The idea of this stage is to keep around each point only the most relevant channels.  In the case of Bovik, Clark and Geisler, this is achieved by labelling each point $x$ of the image with its most active channel : $i(x) = \arg\!\max((R_i)_i)$.  In other terms, only the maximum channel is kept and ``inhibits'' the other ones, which are put to zero. In the method of Voorhees and Poggio, inhibition plays a role by the fact that only the main direction of each bar is kept.  The inhibition process is more sophisticated in Malik and Perona, but the basic idea is the same : the most active channels are reinforced and the comparatively less active are lowered or put to zero.

\subsubsection*{Stage 4: Texture boundary detection.}

In all cases, this stage is very rough and only used to show that discrimination is indeed achieved.  It follows the Hildreth and Marr theory of edge detection : to compute the boundaries by finding the points at which the gradient is maximum.  However, since the channels obtained after the three preceding stages oscillate much, this implies a preliminary low pass filtering of each channel.  The low pass filter is a Gaussian in both Bovik, Clark and Geisler (with a size of about 3/2 times the size of the analysing Gabor function) and also in Malik and
Perona, where the size is found heuristically.  Voorhees and Poggio use a
filter with a size of about five times the size of the blobs or bars, and
more.
\medskip

\subsubsection*{Relation with the texton doctrine.}

Do these computational theories match the conceptual construction of
Julesz ?   
\begin{description}
\item[a)] The axiom 1 of Julesz, implying the parallelism of the computation in
preattentive vision, is respected at all the stages of the preceding models. 
Indeed, they all are only made of  spatially localized computations, which
could be made in parallel.
\item[b)] The Julesz definition of textons, which was restricted to line drawings, is generalized by these theories in a straightforward way.  They all 
compute local densities of some attributes which can be called ``textons''. 
Indeed, the channels obtained after the second stage give the density of
some local, oriented and symmetric patterns which look like bars, blobs, or
eventually pairs of concentric blobs (in Malik and Perona) and groups of
parallel bars.  However, there is an important improvement in Malik and
Perona and Bovik, Clark and Geisler with respect to the texton theory : the
density of textons is ``implicit'' (they are not properly counted) and each
computed channel gives a more quantitative information than only a
density : the weights of textons are kept for the final discrimination. 
Voorhees and Poggio, however follow a very litteral version of the texton
doctrine : they do not associate to a given texton any weight.  Only
presence or absence matters.
\item[c)]  Axiom 3 : {\em ``Only densities of textons matter''} is also respected since the stage 4 implies the loss of the precise location of each texton and only keeps its local density. The low pass filter mentionned in stage 4 above
corresponds exactly to the ``$\Delta$-neighbourhood'' introduced by Julesz.
\end{description}
To summarize, the stages 1 and 2 of the preceding computational theories
calculate the texton channels, and the stage 4 their densities and gradient. 
Now, these theories use all another tool, which apparently does not
correspond to any exigence of the texton doctrine : the ``collateral
inhibition''.   In Bovik, Clark and Geisler, this inhibition is particularly
strong, since only the most active channel is kept to characterize locally
the texture.  We think that this point is a serious divergence from the
texture discrimination theory.  As we explained in our presentation of the
Malik and Perona theory, the collateral inhibition implies that if two
textures have the same dominant channel density, they will remain undiscriminated.  By this way, the ``naive'' theory, in principle rejected,  of an intrinsic characterization of the textures is reintroduced, and the well admitted principle that in perception only contrast matters  is violated.  In this context, the statement of Malik and Perona that inhibition improves discrimination seems to be true only for pairs of textures having  distinct dominant channels.   However, the Malik and Perona collateral inhibition plays another role in their discrimination algorithm, which might explain its usefulness.   Inhibition is made before  the convolution, that is, before the loss of exact localization of textons.  Therefore, inhibition is used for creating new and ``hidden'' textons, whose shape is unfortunately not showed or discussed in the paper.  However, as we shall see in the next section, this inhibition allows to distinguish textures made of opposite
patterns.


\section[Comment choisir les canaux de textons : introduction]{How to choose the texton channels : an insight.}

The question of which linear filters to choose for the first (linear)
stage of the discrimination algorithm is a priori completely solved by the
Wavelet theory : almost any zero-mean filter since it gives completeness of the representation \cite{GroM}. If one seeks for velocity, it is however better to choose orthogonal or biorthogonal filters~\cite{Coh,FroM}. Now, since the local mean of the signal (brightness) is quite relevant for discrimination, it seems to be necessary to add to a complete wavelet
analysis low pass filters.  One could think that the wavelet theory makes
every discussion about the ``right filters'' irrelevant.  That is not really the
case, because of the interaction with the subsequent nonlinear stages of
the algorithm.
\smallskip 

For example, Beck observed that a region filled with vertical Ts is readily
distinguished from one filled with tilted Ts but not from one filled with
vertical Ls.  He attributed this to the different distribution of oriented
line segments present in the former case but not in the latter.  However,
Bergen and Julesz~\cite{BergenJ2} found that a region of randomly oriented Xs segregated from one filled with randomly oriented Ls, in spite of the identical
distribution of oriented line segments in the two cases.  They suggested
that this discrimination might be based on the density of such features as
terminators, corners, and  intersections within the patterns.  J.R. Bergen
and E.H. Adelson~\cite{BergenA} noted that simpler, lower level mechanisms tuned
for size may be sufficient to explain this discrimination.  They tested this
by varying the relative sizes of the Xs and the Ls; when they produced equal
responses in size-tuned mechanisms they were hard to discriminate, and
when they produced different size-tuned responses they were easy to
discriminate.  Those size-tuned filters are simply means on disks, and the
Xs and Ls, when resized to have the same diameter, have their grey level
redefined in order to have this mean value equal.  Then, the textures are no
more discriminable.  The conclusion of this discussion is that almost
linear simple algorithms can be sufficient where the intuition suggests
much more non linear mechanisms.  Let us now begin with the discussion of
what these nonlinearities should be.


\subsubsection*{A) Purely linear mechanisms are inadequate.}

As noticed by Malik and Perona, a model based purely on linear mechanisms
cannot reproduce human performance.  Indeed, consider two textures $\cal A$ and
$\cal B$ which have identical mean brightnesses i.e. identical spatial averages.
Convolving them with a linear filter $F$ results in responses $R_{\cal A}(x,y)$ and $R_{\cal B}(x,y)$ with identical spatial averages. (The value of the power spectra at 0 are identical).  Now, humans can preattentively discriminate some
textures with identical spatial averages.  An example is the even-odd pair
from Julesz, Gilbert and Victor~\cite{JuGV}, or indeed any discriminable texture
pair with identical first order global statistics.  Some nonlinearity in the
system is therefore necessary for texture discrimination.  The simplest
nonlinearities which have been considered are
\begin{description}
\item[-] ``Full wave rectification'', where the response of the $k$-th channel is\\
$R_k(x,y)= |(I\star F_k)(x,y)|\;$  ( \cite{BergenA} ) .
\item[-] ``Energy'' computation, where $R_k(x,y) =  |(I\star S_k)(x,y)|^2 + |(I\star C_k)(x,y)|^2$, \\
and $S_k$, $C_k$ constitute a pair of filters in quadrature phase e.g. Gabor sine and cosine filters ( \cite{SuBG} ).   
\item[-] ``Half wave rectification'', as in the Malik and Perona model discussed
above.
\end{description}
Now, in both full-wave rectification and energy computation, the sign of
the filter response is lost.  Consequently, the response in a full-wave
rectification channel or in an energy channel is identical for micropatterns
$M$ and $-M$, and would remain so after any subsequent processing.  This
results in the prediction that a texture pair composed of micropatterns $M$
on one side and $-M$ on the other (bright bars and dark bars, say) cannot be
discriminated.  Since we can discriminate easily many such texture pairs, it is obvious that these nonlinearities can not  be part of all
the channels of the visual pathway that performs texture perception.

\subsubsection{B) Need for a second nonlinearity.}

Malik and Perona have experimented that a model of texture discrimination
that uses ``half-wave rectification'' as the only nonlinearity successfully
explains human performance on a number of examples.  However it cannot
explain the easy segmentation of any texture pair composed of
micropatterns $M$, and $-M$.  For any zero-mean filter $F$ the pooled half-wave
rectified responses are insufficient for discriminating between the two
textures.  In fact the average response is zero, $\int M\star F =0$, hence the positive and negative parts of the responses of each texture have the same average, and therefore, because of the sign symmetry, the positive parts (and the
negative parts) of the responses of the two textures also have the same
average: $\int(M\star F)^+= \int(M\star F)^- = \int(-M\star F)^+$ .  Segmentation is therefore impossible for any  channel corresponding to zero-mean filters.  However, if the system $F_k$ is complete, it is clear that the whole information concerning the signal is kept in $(I\star F_k)^\pm$. By taking, for instance, the squares of these values, we avoid apparently the preceding objection concerning textures made of patterns $M$ and $-M$. Thus the true reason for the complicated inhibition mechanism ideated by Malik and Perona must be found elsewhere : it created nonlinear positional interaction between blob an bar detectors of
the same intensity, introducing therefore the possibility of a discrimination based on angles, corners, and so on.  Therefore, the Malik and Perona inhibition stage is an authentic texton analyser.  

It suffers, however, the basic defect which we mentioned in the preceding
section.  To illustrate this problem, let us consider the example analysed
in detail by those authors. Take a texture $\cal A$ made of the regular
distribution of a zero-mean micropattern $M$ having a strong black bar
between two thiner white bars on grey background.  The texture $\cal B$ made
with $-M$ is discriminable from $\cal A$. Roughly speaking, the
collateral inhibition of Malik and Perona works as follows.  In texture $\cal A$, the stronger black bar will remain unaltered and ``inhibit'' the close white
bars, the result being that the  ``white bar'' channel will be put to zero
after the inhibition (before the inhibition, it was positive).  Similarly, the
``white bar'' channel will be unaltered in texture $\cal B$ and the ``black bar'' channel will vanish. Thus, both channels will allow a strong discriminability for the considered texture.

In order to make more precise our criticism of the last section, let us
precise an unfortunate consequence of this mechanism: consider the new
pair made of texture $\cal A$ and texture $\cal A'$ obtained from texture $\cal A$ by removing the left white bar. Then the collateral inhibition will make this
difference lost. An obvious solution could be to keep the original channels
$R_k$ together with the ``post inhibition'' channels.


\subsubsection*{C)  Choice of the filters according to some incompleteness of human vision.}

One can find in Malik and Perona the following statement:
\begin{quote}
\em Our model used only channels corresponding to even symmetric filters.  This choice was based on an interpretation of some experimental results of Rentschler, Hubner and Caelli~\cite{RenHC} who found that textures composed of mirror image compound Gabor signals were indistinguishable even when the individual
micropatterns were easily discriminated. There was no
difficulty in discriminating textures composed of non mirror-image
compound Gabor signals.  We attribute  the failure to discriminate
preattentively textures of mirror images micropatterns to a lack of
utilisation of channels corresponding to odd symmetric filters.
\end{quote}
As we wrote in the introduction of this section, this argument is not valid, since complete signal representations can of course be given by symmetric
filters, as it is the case for the wavelet transforms of Grossmann and
Morlet~\cite{GroM} or the biorthogonal transforms of Cohen, Daubechies and Feauveau~\cite{CohDF}.

\subsubsection*{D) A method for evaluating the relevance and necessity of a given subclass of filters for a successful discrimination.}

Malik and Perona give the following interesting comment :
\begin{quotation}
\em Julesz and Kr\"{o}se~\cite{JuK} studied textures composed of Ls and +s which Bergen Adelson~\cite{BergenA} say segmentable using the output of a simple
center-surround Laplacian of Gaussian filter.  Julesz and Kr\"{o}se decomposed this image into a series of bandpass filtered images using the Laplacian pyramid technique.  Levels 2, 3 and 4 of the pyramid appeared to
be the ones showing a difference between the texture of Ls and the texture
of +s, and hence responsible for texture discrimination. Julesz and Kr\"{o}se
constructed a new image where these levels had been replaced by uniform
grey.  The textures however remained highly discriminable, casting doubts
on the validity of Bergen and Adelson's explanation. (...)

Julesz (personal communication) has suggested that the technique of
removing frequency bands used by Julesz and Kr\"{o}se can be used to generate
counterexamples for theories which do not have any nonlinearity before 
the linear filtering stage.  We have tried this on the +-L and the
triangle-arrow textures deleting the frequencies that appeared to be used
by our algorithm for segmentation.  A segmentable texture obtained this
way would falsify our theory, or, at least, show that we  need to add more
filters to our implementation.  As observed above, for the +-L texture
every frequency band appears to contribute to segmentation, producing the
trivial result that only a blank image is not segmentable.   In the
triangle-arrow texture filtering away the relevant frequency bands
considerably reduces discriminability.
\end{quotation}

\clearpage

\section[Un algorithme de discrimination de textures]{Design of a texture discrimination algorithm.}


Let us first quote a remark of J. Beck, A. Sutter and R. Ivry~\cite{BecSI}
\begin{quote}
\em Wertheimer proposed that visual processes explicitly link element shapes
as a function of their proximity and as a result of differences in the
outputs of spatial frequency channels.  The outputs of the spatial
frequency channels first define element shapes.  Texture segregation
occurs as a result of feature differences of the element shapes or of the
higher order texture elements formed through local linking processes.
\end{quote}
The aim of this section is to describe a fast (possibly real time)  and
universal image segmentation algorithm.  The properties of this algorithm, 
are  :
\begin{enumerate}
\item It is multiscale and pyramidal. In other terms, it will not only compute
one segmentation, but 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. 
This corresponds to Marr's remark that textures ``live'' at several scales. 
Therefore, a discrimination algorithm should give different kinds of
segmentations which depend on the scale.
\item As a consequence of this pyramidal structure, the algorithm will be a
linear time algorithm, that is, the computation time will be exactly 
proportional to the size of the datum. Moreover, this algorithmic
structure will make it accessible to efficient hardware implementation.
\item The algorithm is universal, that is, does not depend on any a priori
knowledge on the statistics of the image. Texture discrimination is
achieved according to a universal criterion depending on very few
parameters. More precisely, a picture is defined by a certain number of
channels (grey level, colour levels, integrodifferential channels obtained
by fast wavelet transform). In our segmentation algorithm, the only
parameters are the weights attached to each channel, that is, the
importance accorded to each channel as a segmentation criterion.  
\item This algorithm has been constructed by putting together several
theories :
\begin{description}
\item[-] the textons theory.
\item[-] the energy methods in image segmentation introduced by Geman and Geman, Cooper, Blake and Zisserman, Mumford and Shah\ldots
\item[-] the Wavelet transform theory of Meyer, Mallat and Cohen, which 	unifies the theory of recursive filtering and pyramidal schemes.
\end{description}
\item The segmentations provided by the algorithm are mathematically
proved to have a large range of good topological and numerical properties,
including compactness of the set of approximate solutions, convergence of
minimizing sequences made of  finer and finer solutions, smoothness of
the locally optimal solutions, completeness of the multiscale
representation, a priori estimates on the size of the zones of the
segmentations, and so on  (for details, see chapter \ref{chSeg},\ref{chReg},\ref{chIm-Exp}).
\end{enumerate}
\mbox{}
\smallskip
\newline
We follow the ideas of David Marr~\cite{Marr3} concerning the ``raw primal
sketch''.  According to this theory, which we mentionned above, the
grouping process of the  human  visual system should be based on the
detection of local features which from the mathematical viewpoint are
simply differential or semilocal integrodifferential operators like the
derivatives or a convolution by Gaussian. As we have seen in the
preceding sections, the preattentive texture discrimination deeply depends
on the fact that at least one of the features has a bigger or lower density. 

It is important to note that most of the channels introduced by the
algorithms discussed in section~\ref{sec_TeEx} are linear operators which, according to the Wavelet theory, can be computed at each scale in linear time by a
pyramidal scheme (also called in this context quadrature mirror filter~\cite{Coh}, \cite{EsG}).   

The wavelet transform allows to compute a multiscale gradient in every direction in linear time (by a quadrature mirror filter). Since, as recalls David Marr, textures live independently at different scales, it  will be much easier to
get discrimination of most textures with a fast multiscale analysis.  One
can for instance use the Daubechies filters~\cite{Daub1,Daub2}, which can be computed with quadrature mirror filters having very few  coefficients (eight
coefficients are enough for a smooth wavelet with two zero moments).  In
a work in collaboration with Jaffard and Journ\'e, Daubechies has proved a
fast algorithm for a variant of Gabor filtering (\cite{DaubJJ}).  Fast Gabor filtering will
also provide cheap channels for our segmentation algorithm, which prove
very useful for almost periodic textures.
\smallskip
\newline 

Note however that the human eye is by no means perfect in texture
discrimination and that it can reasonably be argued that a discrimination
algorithm could be more accurate and discriminate textures which are not
directly accessible to the human eye. In our opinion, a successful
computational model of texture discrimination should do better than the
human eye in some cases, and therefore be used as an enhancement
operator.  
\medskip
\newline
Let us summarize the assumptions on which we base our segmentation
algorithm :
\begin{itemize}
\item We assume, following the theory of Beck and Julesz and some recent 
experimental and computational confirmation of it (Malik and Perona) that
a reasonable number of channels defined on the image is enough in order
that for any pair of preattentively different textures, at least one of the
channels will help to discriminate them.
\item We are not able now to  say which channels are necessary or sufficient in
order to get a discrimination similar to that of the human eye.  Now, our
universal segmentation algorithm is designed for fast specific
applications, but also  as a fast and robust experimental device allowing
decisive progress in  the question of which channels are necessary in order
to match the human visual performance.
\end{itemize}
\bigskip

\subsubsection*{Examples.}

\label{sec_tex_examples}Let $g=(g_1, \ldots , g_n)$ be the initial data calculated from the picture $\tilde{g}$ and $u=(u_1, \ldots ,u_n)$ the piecewise constant estimate ( it turns out that $u_i$ is the mean value of $g_i$ on each connected component). Using the functional
$$\int_\Omega \|u-g\|^2_{pond.}+\lambda\cdot\ell(K)\;,$$
where $\|.\|_{pond.}$ is a weighted norm, we calculate a 2-normal segmentation ( see chapters \ref{chReg},\ref{chIm-Exp}) .
\medskip
\newline
The initial data $g$ for the experiments related below is typically given by an oversampled Haar-Wavelet transform of the picture $\tilde{g}$ : $WT(\tilde{g}) \longrightarrow g$.
\medskip
\newline
The aim of our experiences is to get a verification of the Julesz doctrine : we stop our region growing if the desired number of regions is reached ( e.g. if there are two textures we proceed until we have a partition in two regions of our image) . If the discrimination is succesfull ( i.e the two regions correspond to the textures' location) one can say that the used channels  are able to discriminate the given textures ( it is important to notice that we don't use the grey-channel information ).
\medskip
\newline
The experimentations have been done in collaboration with Christian Lopez at CEREMADE. We used Brodatz pictures (see~\cite{Bro}) and a synthetic image which illustrates our example of page~\pageref{TextA_Ad} . See the following pages.

%-----fig_Text2a-----
\begin{figure}[htb]
  \insertps{figures/Text2a.PS}{80mm}{33mm}
  \caption{Above two Brodatz textures, below the boundary calculated ($\Delta$-neighbourhood of 16 pixels, level of wavelet transform $J=3$) .}
  \label{fig_Text2a}
\end{figure}
%--------------------

%-----fig_Text2b+4-----
\begin{figure}[htb]
  \insertps{figures/Text2b+4.PS}{120mm}{13mm}
  \caption{Left part : two Brodatz textures, right part : three different Brodatz textures. Below each the boundary calculated (same parameters : $\Delta$-neighbourhood of 16 pixels, level of wavelet transform $J=3$) .}
  \label{fig_Text2b+4}
\end{figure}
%----------------------

%-----fig_Seg_TextA_Ad-----
\begin{figure}[htb]
  \insertps{figures/Seg_TextA_Ad.PS}{160mm}{35mm}
  \caption{Above the textures : on the left hand one dominant channel; on the right hand the same dominant channel with a weak second channel. Below the boundary calculated ($\Delta$-neighbourhood of 16 pixels, level of wavelet transform $J=2$) .}
  \label{fig_Seg_TextA_Ad}
\end{figure}
%--------------------------
